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 $\varphi (n)$, which implies breaking RSA

Let $p$ be prime.

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

Corollary. A number in $\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}$ has at least $d$ $d$^th roots in $\mathbb{\mathbb{Z}}/p\mathbb{\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\mathrm{\forall }x\in G$
2. Every $x$ has a multiplicative inverse: $x*y=y*x=e$
3. $*$ is associative
4. $*$ is commutative

Examples:

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

Cyclic

An Abelian group is cyclic when it has a generator

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

Note: Finding generators is not trivial

Corollary

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

Corollary: Exactly half of the elements of $(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}{)}^{*}$ (for odd prime $p$ )are squares. They are $\{g^0,g^2,g^4,\dots ,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}(\mathrm{mod}n)$?

First, if you have $\sqrt{11}(\mathrm{mod}pq)$, you must certainly have $\sqrt{11}(\mathrm{mod}p)$ and $\sqrt{11}(\mathrm{mod}q)$.

For $p=107$, $p\equiv 3(\mathrm{mod}4)$:

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

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

For $q=127$, $p\equiv 3(\mathrm{mod}4)$:

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

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

Can we find an $x$ with the following?

$\begin{array}{rl}x& \equiv \pm 15(\mathrm{mod}107)\\ x& \equiv \pm 30(\mathrm{mod}127)\end{array}$

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{array}{rl}\sqrt{11}& =\{\pm 15\cdot 127\left(\frac{1}{127}(\mathrm{mod}107)\right)\pm 30\cdot 107\cdot \left(\frac{1}{107}(\mathrm{mod}127)\right)\}\\ & =\{\pm 15\cdot 127\cdot 91\pm 30\cdot 107\cdot 19\}\\ & =\{\pm 10287\pm 6634\}\end{array}$

In summary, for $p\equiv 3(\mathrm{mod}4)$,

• compute Legendre symbol
• find

BUT for $p\equiv 1(\mathrm{mod}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(\mathrm{mod}4)$, you can find $\sqrt{a}(\mathrm{mod}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 $t{2}^s$ with odd $t$ (easy via binary search)
3. let $e=0$
4. for $i$ from 2 to $s$, do
5. if ${\left(a{g}^{-e}\right)}^{\frac{p-1}{2^i}}\ne 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}(\mathrm{mod}p)$?

• $\left(\frac{11}{104729}\right)=1$, so square root exists
• $p\equiv 1(\mathrm{mod}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\ne 1$, so try e = 2
4. e = 2: ...
5. ...

Binary Search

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

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