MATH 470 Lecture 7

« previous | Tuesday, February 5, 2013 | next »

RSA

1. Take large blocks of text
2. convert letters to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}/26\mathbb{Z}}
3. convert that block into a large integer base 26
4. perform modular arithmetic on blocks

Sage

• ord(char) converts char to a number
• list(string) produces an array of characters
• map(func, array) does what it says.

Hardness of Multiplication and Factoring

Recall:

• Grade school algorithm takes $O(d^{2})$ bit operations
• Fast-Fourier Multiplication takes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(d \log{(d)} \log{(\log{(d)})})} bit operations

Factoring a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} -digit integer takes a lot longer: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(2^{\frac{d}{4}} d(d+\log{d}))} bit operations (Pollard-??? method)

Breaking RSA Can be done via integer factorization: This is why we care about complexity.

To factor $n$, we could do trial division by all primes up to ${\sqrt {n}}$. If $n$ has $d$ digits, then this would be:

$O({\sqrt {n}}\,d\,\log {(d)}\,\log {(\log {(d)})})=O(10^{\frac {d}{2}}\,d\,\log {(d)}\,\log {(\log {(d)})})$

We'll study more about factoring soon: in fact square roots mod $n$ are very important in factoring.

Warm-up

Since FLT says $a^{p-1}\equiv 1{\pmod {p}}$ for $p\nmid a$, can we use this for square roots?

Does $sqrt(3)$ exist mod 7?

We know $3^{7-1}\equiv 1{\pmod {7}}$ by FLT.

if \sqrt{3} did exist, we would have $sqrt{3}^{6}\equiv 1{\pmod {7}}$

However, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{3}^6 \equiv 3^3 \equiv 27 \equiv -1 \pmod{7}} (contradiction!)

What's up?

Legendre Symbol

More generally, we define

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \frac{a}{p} \right) = \begin{cases} 0 & p \mid a \\ 1 & p \nmid a \text{ and } a \text{ is a square mod } p \\ -1 & p \nmid a \text{ and } a \text{ is not a square mod } p \end{cases}}

Examples:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \left( \frac{3}{7} \right) &= -1 \\ \left( \frac{4}{p} \right) &= 1 \end{align}}

Lemma

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{p} \right) = a^{\frac{p-1}{2}} \pmod{p}}

The fastest current factoring algorithm appears to have complexity

<math>O \left( \mathrm{e}^{d^{\frac{1}{3}}} \, d^{\frac{2}{3}} \right)