MATH 470 Lecture 7

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

RSA

1. Take large blocks of text
2. convert letters to $\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 $O(d\log {(d)}\log {(\log {(d)})})$ bit operations

Factoring a $d$-digit integer takes a lot longer: $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 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} digits, then this would be:

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(\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 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 n} are very important in factoring.

Warm-up

Since FLT says 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 a^{p-1} \equiv 1 \pmod{p}} for 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 p \nmid a} , can we use this for square roots?

Does 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)} exist mod 7?

We know 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 3^{7-1} \equiv 1 \pmod{7}} by FLT.

if \sqrt{3} did exist, we would have 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 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)