MATH 470 Lecture 7

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

RSA

1. Take large blocks of text
2. convert letters to $\mathbb{\mathbb{Z}}/26\mathbb{\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(\mathrm{mod}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(\mathrm{mod}7)$ by FLT.

if \sqrt{3} did exist, we would have $sqrt{3}^6\equiv 1(\mathrm{mod}7)$

However, ${\sqrt{3}}^6\equiv 3^3\equiv 27\equiv -1(\mathrm{mod}7)$ (contradiction!)

What's up?

Legendre Symbol

More generally, we define

$\left(\frac{a}{p}\right)=\{\begin{array}{ll}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{array}$

Examples:

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

Lemma

$\left(\frac{a}{p}\right)=a^{\frac{p-1}{2}}(\mathrm{mod}p)$

The fastest current factoring algorithm appears to have complexity

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