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 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} for the kinds of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} just stated in time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\log{n})^{O(1)}} , then you can factor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} in expected time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is an odd prime with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p = 3 \pmod{4}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \tfrac{a}{p} \right) = 1} , then the square roots of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} are exactly Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pm a^{\frac{p+1}{4}} \pmod{p}}

Proof. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \tfrac{a}{p} \right) = 1} , then (by Euler),

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{\frac{p-1}{2}} = 1}

Now Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \equiv 3 \pmod{4}} , so

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \frac{p+1}{4} &= \frac{(4k+3)+1}{4} \\ &= \frac{4k+4}{4} \\ &= k+1 \end{align}}

So Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \pm a^{\frac{p+1}{4}} \right)^2 = \left( \pm a^{k+1} \right)^2 = a^{2k+2} = a}

Now Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{\frac{p-1}{2}} = a^{\frac{4k+3-1}{2}} = a^{2k+1} = 1}

So Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{2k+2} = a \cdot a^{2k+1} = a \cdot 1 = a}