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 $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, ${\sqrt {3}}^{6}\equiv 3^{3}\equiv 27\equiv -1{\pmod {7}}$ (contradiction!)

What's up?

Legendre Symbol

More generally, we define

$\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:

${\begin{aligned}\left({\frac {3}{7}}\right)&=-1\\\left({\frac {4}{p}}\right)&=1\end{aligned}}$

Lemma

$\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)