MATH 470 Lecture 8

« previous | Thursday, February 7, 2013 | next »

Midterm Exam on Thursday, March 21, 2013

Recursive Squaring

What is $7^{818}(\mathrm{mod}1637)$?

Note that 818 = 512 + 256 + 32 + 16 + 2, so we can compute:

• $7^2\equiv 49(\mathrm{mod}1637)$
• $7^4\equiv 49^2\equiv 764(\mathrm{mod}1637)$
• $7^8\equiv 764^2\equiv 924(\mathrm{mod}1637)$
• $7^{16}\equiv 924^2\equiv 899(\mathrm{mod}1637)$
• $7^{32}\equiv 899^2\equiv 1160(\mathrm{mod}1637)$
• $7^{64}\equiv 1160^2\equiv 1623(\mathrm{mod}1637)$
• $7^{128}\equiv 1623^2\equiv 196(\mathrm{mod}1637)$
• $7^{256}\equiv 196^2\equiv 765(\mathrm{mod}1637)$
• $7^{512}\equiv 765^2\equiv 816(\mathrm{mod}1637)$

$\begin{array}{rl}{7}^{512}\cdot 7^{256}\cdot 7^{32}\cdot 7^{16}\cdot 7^2& \equiv \underbrace{816\cdot 765}\cdot \underbrace{1160\cdot 899}\cdot 49(\mathrm{mod}1637)\\ & \equiv 543\cdot \underbrace{71\cdot 49}(\mathrm{mod}1637)\\ & \equiv 543\cdot 205(\mathrm{mod}1637)\\ & \equiv 1636(\mathrm{mod}1637)\end{array}$

We poerformed a total of 13 multiplications!

Legendre Symbol

Euler's Criterion

Euler's Criterion: If $a\in \mathbb{\mathbb{Z}}$ and $p$ is an odd prime, then

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

Proof

First, if $p\mid a$, then $a\equiv 0(\mathrm{mod}p)$ and thus $\left(\frac{0}{p}\right)=0$. Indeed $0^{\frac{p-1}{2}}=0$.

Assume $p\nmid a$, then it's enough to show

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

If $\left(\frac{a}{p}\right)=1$ then $a=x^2(\mathrm{mod}p)$ for some $x\in {(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$. So $a^{\frac{p-1}{2}}={\left(x^2\right)}^{\frac{p-1}{2}}=x^{p-1}=1(\mathrm{mod}p)$ by Fermat's little theorem.

Conversely, using the theorem below, let $a=g^k$ for some $k\in \{0,\dots ,p-2\}$ and generator $g$. Now

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

Since

$g$

is a generator, any power of

$g\equiv 1(\mathrm{mod}p)$

must have exponent divisible by

$p-1$

. So

$\frac{k(p-1)}{2}=N(p-1)$

implies that

$k$

is divisible by 2. Therefore,

$a=g^k$

is a square.

Q.E.D.

Theorem

For any prime $p$, ${(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$ as a multiplicative generator (primitive root), that is, there is a $g\in \{2,\dots ,p-1\}$ with

$\{g^0=1,g^1,g^2,\dots ,g^{p-2}\}=\{1,2,3,\dots ,p-1\}$

In sage, you can say

sage: R = Integers(13)

to use $R=(\mathbb{\mathbb{Z}}/13\mathbb{\mathbb{Z}})$

sage: R.multiplicative_generator()
2

So $\{2^0=1,2,4,8,3,6,12,9,5,10,7\}=\{1,\dots ,12\}$

Why do we care about modular square roots?

Suppose you had a magic machine that quickly computed square roots mod any integer. Then you can break RSA!

To break RSA, you need one of: luck, treachery, knowing either $\varphi (n)$ or $p$ and $q$ or $n$'s factorization.

If you know how to compute square roots mod $n$, factoring $n$ is easy

Example

Let $n=988027$.

Pick a random number, e.g. 4

Let's "magically" compute $\sqrt{4}$: $\pm 2(\mathrm{mod}988027)$

Consider $2-(-2)=4$ and $2+(-2)=0$.

• GCD(988027, 4) = 1
• GCD(988027, 0) = 988027

Pick another random number, e.g. 42

There are 4 square roots to 42 mod 98027: 323739, 429421, 558606, and 664288.

• GCD(323739-429421, 988027) = 997
• GCD(323739+429421, 988027) = ...

Thus 997 divides 988027. In particular, $988027=997\cdot 991$

GCD's are relatively easy to compute. Therefore, if we can take square roots quickly, we can factor quickly

In General

Assuming you can find square roots mod $n$ quickly, you can factor as follows:

Input: integer N of form N = p*q, where p and q are large odd primes
Output: p and q
Description:
(1) Pick random k in {1, ..., N-1}
(2) Decide if sqrt(k) mod N exists.
    If not, go to step 1.
(3) Find 2 distinct square roots of k mod N.
    Call them X1 and X2.
(4) If GCD(X1-X2, N) > 1 or GCD(X1+X2, N) > 1, then that number is p or q.
    Divide by it to get q or p
(5) Go to step 1

Theorem: If you can compute square roots mod $n$ for the kinds of $n$ just stated in time $(\log n{)}^{O(1)}$, then you can factor $n$ in expected time $(\log n{)}^{O(1)}$ via our last algorithm.

This theorem is modern, but the ideas go back to Gauss (1777–1855)

Proof will come later.

A consequence of Euler's Criterion:

Corollary

If $p$ is an odd prime with $p=3(\mathrm{mod}4)$ and $\left(\frac{a}{p}\right)=1$, then the square roots of $a$ are exactly $\pm a^{\frac{p+1}{4}}(\mathrm{mod}p)$

Proof. If $\left(\frac{a}{p}\right)=1$, then (by Euler),

$a^{\frac{p-1}{2}}=1$

Now $p\equiv 3(\mathrm{mod}4)$, so

$\begin{array}{rl}\frac{p+1}{4}& =\frac{(4k+3)+1}{4}\\ & =\frac{4k+4}{4}\\ & =k+1\end{array}$

So ${(\pm a^{\frac{p+1}{4}})}^2={(\pm a^{k+1})}^2=a^{2k+2}=a$

Now $a^{\frac{p-1}{2}}=a^{\frac{4k+3-1}{2}}=a^{2k+1}=1$

So $a^{2k+2}=a\cdot a^{2k+1}=a\cdot 1=a$