MATH 470 Lecture 8

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

Midterm Exam on Thursday, March 21, 2013

Recursive Squaring

What is $7^{818}{\pmod {1637}}$ ?

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

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

${\begin{aligned}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{\pmod {1637}}\\&\equiv 543\cdot \underbrace {71\cdot 49} {\pmod {1637}}\\&\equiv 543\cdot 205{\pmod {1637}}\\&\equiv 1636{\pmod {1637}}\end{aligned}}$

We poerformed a total of 13 multiplications!

Legendre Symbol

Euler's Criterion

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

\left({\frac {a}{p}}\right)=a^{\frac {p-1}{2}}{\pmod {p}}

Proof

First, if $p\mid a$ , then $a\equiv 0{\pmod {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)\iff a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}

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

Conversely, using the theorem below, let $a=g^{k}$ for some $k\in \{0,\ldots ,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{\pmod {p}}

Since $g$ is a generator, any power of $g\equiv 1{\pmod {p}}$ must have exponent divisible by $p-1$ . So ${\tfrac {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$ , $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$ as a multiplicative generator (primitive root), that is, there is a $g\in \{2,\ldots ,p-1\}$ with

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

In sage, you can say

sage: R = Integers(13)

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

sage: R.multiplicative_generator()
2

So $\{2^{0}=1,2,4,8,3,6,12,9,5,10,7\}=\{1,\ldots ,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 $\phi (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{\pmod {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{\pmod {4}}$ and $\left({\tfrac {a}{p}}\right)=1$ , then the square roots of $a$ are exactly $\pm a^{\frac {p+1}{4}}{\pmod {p}}$