MATH 470 Lecture 11

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

Inequality Relevant to Primes

For all $c\geq 0$ , $t\geq 1$ , we have

\left(1-{\frac {1}{t}}\right)^{ct}\leq \mathrm {e} ^{-c}

Recall the probability of picking a random number in (1,n) is greater than ${\frac {1}{\ln {n}}}$

So the chances of failing to pick a prime in $k$ tries is $\left(1-{\frac {1}{\ln {n}}}\right)^{k}$

By substituting $k$ for $c$ and $\ln {n}$ for $t$ in the lemma above, the chances of failing to find a prime after $k\ln {n}$ tries is:

\left(1-{\frac {1}{\ln {n}}}\right)^{k}\leq \left(1-{\frac {1}{\ln {n}}}\right)^{k\ln {n}}\leq \mathrm {e} ^{-k}

Therefore, after $k\ln {n}$ tries, the chances of you finding a prime is at least $1-\mathrm {e} ^{-k}$

A more precise estimate on the number of primes less than $x$ ( $\pi (x)$ ) is:

Riemann Hypothesis

(1859; One reformulation)

Complex analysis to number theory

\left|\pi (x)-\mathrm {Li} (x)\right|=O({\sqrt {x}}\,\ln {x})

(Still unproved)

Deeper question: count primes in arithmetic progression (very relevant to cryptography)

               2 3 5 7 11 13 17 19 23 29 31 ...
equiv 3 mod 4:   X   X  X        X  X     X

What about primes of the form $nx+a$ ?

$n$ and $a$ should be relatively prime, so there are $\phi (n)$ many classes

Dirichlet's Theorem

Let π(x; n, a) = number of primes ≤ x which are ≡ a (mod n)

Then $\lim _{x\to \infty }{\frac {\pi (x;n,a)}{\frac {x}{\phi (n)\ln {x}}}}=1\quad \mathrm {GCD} (a,n)=1$

Applied to Riemann Hypothesis, we get the Generalized Riemann Hypothesis:

\left|\pi (x;n,a)-{\frac {1}{\phi (n)}}\,\mathrm {Li} (x)\right|=O_{n}({\sqrt {x}}\,\ln {x})

GRH is a huge problem from analytic number theory and greatly impacts cryptography and algorithms

Jacobi Symbol

if $n=\prod _{i=1}^{k}{p_{i}}^{b_{i}}$ with distinct primes $p_{i}$ , $b_{i}\in \mathbb {N}$ , and $a\in \mathbb {Z}$

We define

\left({\frac {a}{n}}\right)=\prod _{i=1}^{k}\left({\frac {a}{p_{i}}}\right)^{b_{i}}

Note:

Definition is absurd computationally! (requires factoring)
Legendre symbol is a special case of the Jacobi symbol
$\left({\tfrac {a}{n}}\right)$ is not always $a^{\frac {n-1}{2}}{\pmod {n}}$ (e.g. $\left({\tfrac {2}{15}}\right)=1$ , whereas $2^{\frac {15-1}{2}}\equiv 8{\pmod {15}}$
$\left({\tfrac {a}{n}}\right)=1$ need not imply $a$ is a square mod $n$
$\left({\tfrac {a}{n}}\right)=-1$ means $a$ is not a square (i.e. one-sided check for square-ness

Jacobi yield a much faster way to compute Legendre symbols:

Theorem. If $n$ is odd,

$a\equiv b{\pmod {n}}$ and $\mathrm {GCD} (a,n)=1$ then $\left({\tfrac {a}{n}}\right)=\left({\tfrac {b}{n}}\right)$
if $\mathrm {GCD} (a\,b,n)=1$ then $\left({\tfrac {a\,b}{n}}\right)=\left({\tfrac {a}{n}}\right)\,\left({\tfrac {b}{n}}\right)$
$\left({\tfrac {-1}{n}}\right)=\left(-1\right)^{\frac {n-1}{2}}$
$\left({\tfrac {2}{n}}\right)={\begin{cases}1&n\in \{1,7\}{\pmod {8}}\\-1&n\in \{3,5\}{\pmod {8}}\end{cases}}$
Gauss' law of quadratic reciprocity (1796): If $m$ is odd and $\mathrm {GCD} (m,n)=1$ then $\left({\frac {m}{n}}\right)={\begin{cases}-\left({\frac {n}{m}}\right)&m\equiv n\equiv 3{\pmod {4}}\\\left({\frac {n}{m}}\right)&{\text{otherwise}}\end{cases}}$

Example

${\begin{aligned}n&=1,209,387\\a&=600,001\end{aligned}}$

$\left({\frac {a}{n}}\right)=\left({\frac {n}{a}}\right)$ since $n\equiv 3{\pmod {4}}$ but $a\equiv 1{\pmod {4}}$

$\left({\frac {1,209,387}{600,001}}\right)=\left({\frac {9385}{600,001}}\right)$ by property 1

Apply properties 5 and 1 again...

$\left({\frac {600,001}{9385}}\right)=\left({\frac {8746}{9385}}\right)$

Apply property 2...

$\left({\frac {8746}{9385}}\right)=\left({\frac {2}{9385}}\right)\,\left({\frac {4373}{9385}}\right)$

This becomes $1\cdot \left({\frac {4373}{9385}}\right)$ by property 4

Apply 5 and 1 two more times...

$\left({\frac {4373}{9385}}\right)=\left({\frac {639}{4373}}\right)=\left({\frac {539}{639}}\right)$

Now this is the first time $m\equiv n\equiv 3{\pmod {4}}$ , so by property 5 and 1,

$\left({\frac {539}{639}}\right)=-\left({\frac {100}{539}}\right)$

Note that $100=2^{2}\cdot 25$ , so by property 2,

$-\left({\frac {2^{2}\cdot 100}{539}}\right)=-\left({\frac {2}{539}}\right)^{2}\,\left({\frac {25}{539}}\right)=-\left({\frac {25}{539}}\right)$

Now we can compute as normal...

$-\left({\frac {5^{2}}{539}}\right)=-1\cdot 1=-1$

This was a lot faster than if we would have tried to compute $a^{\frac {n-1}{2}}{\pmod {n}}$ . moral: quadratic reciprocity is much faster

Pratt's Theorem

Last lecture, Dr. Rojas claimed that Jacobi symbols lead to a fast randomized primality test. Let's see a related test:

Key idea: verifying vs. deciding NP problems are easily verified, but finding solution is hard

might go back earlier: Kraitchic-Lehmer

n

is prime iff there is an

a\in \left[1,n\right]

with

a^{n-1}\equiv 1{\pmod {n}}

AND

a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}\quad \forall q\mid (n-1)

, where

q

is prime

Compositeness is easily verified: check a short certificate (candidate factor)

What about primality? Pratt's theorem tells us we can find small certificates to verify primality!

Example

$n=617$

Hint: this tree is the short certificate

617, (3)
|-- 2
|-- 7, (3)
|   |-- 2
|   `-- 3, (2)
`-- 11, (2)
    |-- 2
    `-- 5, (2)
        `-- 2

For $n=617$ , $a=3$ works! In other words, $3^{617-1}\equiv 1{\pmod {n}}$ and $3^{\frac {617-1}{q}}\not \equiv 1{\pmod {n}}$ for all $q\mid (n-1)$ . These $q$ are exactly 2, 7, and 11, so to verify if these are prime, we recursively apply Pratt's theorem.