MATH 470 Lecture 9

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

Review

• method to apply fast square roots mod $n$ to factoring.
• (much earlier) fast factoring implies fast computation of $\phi (n)$, which implies breaking RSA

Let $p$ be prime.

Proposition. A polynomial $(f\in \mathbb {Z} /p\mathbb {Z} )[x]$ of degree $d$ has at most $d$ roots in $\mathbb {Z} /p\mathbb {Z}$.

Corollary. A number in $\mathbb {Z} /p\mathbb {Z}$ has at least $d$ $d$^th roots in $\mathbb {Z} /p\mathbb {Z}$ for prime $p$.

Proof. ${\sqrt[{d}]{a}}$ is a root of $x^{d}-a$, which has degree $d$.

We'll just focus on $d=2$.

Can $a$ have 0 square roots mod 7? (yes, 6) Can $a$ have 1 square root mod 7? (yes, 0, and it's the only one. Any other would have ± that number)

Abelian Group

An Abelian Group $(G,*)$ is a set with a multiplication operation satisfying certain axioms:

1. There is a multiplicative identity $e$: $e*x=x*e=x\quad \forall x\in G$
2. Every $x$ has a multiplicative inverse: $x*y=y*x=e$
3. $*$ is associative
4. $*$ is commutative

Examples:

• $(\mathbb {R} ,+)$ with identity 0
• $(\mathbb {R} \setminus \{0\},*)$ with identity 1
• $(\mathbb {Z} /p\mathbb {Z} ,+)$ with identity 0
• $((\mathbb {Z} /p\mathbb {Z} )^{*},*)$ with identity 1

Cyclic

An Abelian group is cyclic when it has a generator

Example: $(\mathbb {Z} /29\mathbb {Z} )^{*}$ is cyclic with generator 2 in that $\{2^{0}=1,2^{1},2^{2},\ldots ,2^{2}7{\pmod {29}}\}=\{1,2,4,\ldots ,28\}$

Note: Finding generators is not trivial

Corollary

Theorem: $(\mathbb {Z} /p\mathbb {Z} )^{*}$ is cyclic.

Corollary: Exactly half of the elements of $(\mathbb {Z} /p\mathbb {Z} )^{*}$ (for odd prime $p$ )are squares. They are $\{g^{0},g^{2},g^{4},\ldots ,g^{p-1}\}$

Corollary Puzzle

How can we find a quadratic non-residue (not a square) mod 982741? (choose a prime less than $p$)

Finding non-squares mod $p$ is easy with 50% success probability!

Working with Square Roots mod $pq$

Idea: work mod $p$, then mod $q$, then piece together with Chinese Remainder Theorem.

If $p$ and $q$ are the primes 107 and 127, and $n=pq=13589$. What is/are ${\sqrt {11}}{\pmod {n}}$?

First, if you have ${\sqrt {11}}{\pmod {pq}}$, you must certainly have ${\sqrt {11}}{\pmod {p}}$ and ${\sqrt {11}}{\pmod {q}}$.

For $p=107$, $p\equiv 3{\pmod {4}}$:

$\left({\frac {11}{107}}\right)=11^{\frac {107-1}{2}}=11^{53}=1{\pmod {107}}$, so it is a square, and since $11\neq 0$, it has two roots. They are:

${\sqrt {11}}\in \left\{11^{\frac {p+1}{4}},-11^{\frac {p+1}{4}}\right\}=\{\pm 15\}$

For $q=127$, $p\equiv 3{\pmod {4}}$:

$\left({\frac {11}{127}}\right)=11^{\frac {127-1}{2}}=11^{63}=1{\pmod {127}}$, so it is a square and has two roots. They are:

${\sqrt {11}}\in \left\{11^{\frac {p+1}{4}},-11^{\frac {p+1}{4}}\right\}=\{\pm 30\}$

Can we find an $x$ with the following?

${\begin{aligned}x&\equiv \pm 15{\pmod {107}}\\x&\equiv \pm 30{\pmod {127}}\end{aligned}}$

Yes! There are four possible combinations of the above, and we can find all of them by the Chinese Remainder Theorem.

Wait, there are 4 square roots?

There are 4 roots (no more) because it has to simultaneously be a root of each of the prime factors. There are only four possibilities for $n=pq$

To find our square roots, it's helpful to know $x$ and $y$ with $107x+127y=1$ (Extended Euclidean Algorithm): $(x,y)=(19,-16)$

The Chinese Remainder Theorem says that

${\begin{aligned}{\sqrt {11}}&=\{\pm 15\cdot 127\left({\frac {1}{127}}{\pmod {107}}\right)\pm 30\cdot 107\cdot \left({\frac {1}{107}}{\pmod {127}}\right)\}\\&=\{\pm 15\cdot 127\cdot 91\pm 30\cdot 107\cdot 19\}\\&=\{\pm 10287\pm 6634\}\end{aligned}}$

In summary, for $p\equiv 3{\pmod {4}}$,

• compute Legendre symbol
• find

BUT for $p\equiv 1{\pmod {4}}$, you can compute square roots mod $p$ efficiently, but it looks like randomness is unavoidable.

Tonelli's Algorithm

Tonelli (1891)

Given any odd prime $p\equiv 1{\pmod {4}}$, you can find ${\sqrt {a}}{\pmod {p}}$, should it exist, as follows:

1. Find a non-square mod $p$ (call it $g$) (easy with 50% probability)
2. Write $p-1$ in the form $t2^{s}$ with odd $t$ (easy via binary search)
3. let $e=0$
4. for $i$ from 2 to $s$, do
5. if $\left(ag^{-e}\right)^{\frac {p-1}{2^{i}}}\neq 1$, then $e=e+2^{i-1}$
6. end
7. $h=a\,g^{-e}$
8. ${\sqrt {a}}=\{\pm g^{\frac {e}{2}}h^{\frac {t+1}{2}}\}$

Example

For $p=104729$, what is ${\sqrt {11}}{\pmod {p}}$?

• $\left({\frac {11}{104729}}\right)=1$, so square root exists
• $p\equiv 1{\pmod {4}}$, so we have the nasty case

1. Find a non-square: 42? non-square! (first guess!)
2. 104729 - 1 = 104728 = 2³ · 13091
3. e = 0: $11^{\frac {p-1}{2^{2}}}=11^{26192}=31003\neq 1$, so try e = 2
4. e = 2: ...
5. ...

Binary Search

${\begin{aligned}2&\mid 104728\\2^{2}&\mid 104728\\(2^{2})^{2}&\nmid 104728\\2^{3}&\mid 104728\end{aligned}}$

Final Note: A key to using RSA in practice is generating primes. How do we do this? (understand distribution of primes)