MATH 470 Lecture 11

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

Inequality Relevant to Primes

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

${(1-\frac{1}{t})}^{ct}\le {\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 ${(1-\frac{1}{\ln n})}^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:

${(1-\frac{1}{\ln n})}^k\le {(1-\frac{1}{\ln n})}^{k\ln n}\le {\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

$|\pi (x)-\mathrm{L}\mathrm{i}(x)|=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 $\varphi (n)$ many classes

Dirichlet's Theorem

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

Then $\underset{x\to \mathrm{\infty }}{\lim }\frac{\pi (x;n,a)}{\frac{x}{\varphi (n)\ln x}}=1\mathrm{G}\mathrm{C}\mathrm{D}(a,n)=1$

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

$|\pi (x;n,a)-\frac{1}{\varphi (n)}\mathrm{L}\mathrm{i}(x)|=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{\mathbb{N}}$, and $a\in \mathbb{\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(\frac{a}{n}\right)$ is not always $a^{\frac{n-1}{2}}(\mathrm{mod}n)$ (e.g. $\left(\frac{2}{15}\right)=1$, whereas $2^{\frac{15-1}{2}}\equiv 8(\mathrm{mod}15)$
• $\left(\frac{a}{n}\right)=1$ need not imply $a$ is a square mod $n$
• $\left(\frac{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,

1. $a\equiv b(\mathrm{mod}n)$ and $\mathrm{G}\mathrm{C}\mathrm{D}(a,n)=1$ then $\left(\frac{a}{n}\right)=\left(\frac{b}{n}\right)$
2. if $\mathrm{G}\mathrm{C}\mathrm{D}(ab,n)=1$ then $\left(\frac{ab}{n}\right)=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$
3. $\left(\frac{-1}{n}\right)={(-1)}^{\frac{n-1}{2}}$
4. $\left(\frac{2}{n}\right)=\{\begin{array}{ll}1& n\in \{1,7\}(\mathrm{mod}8)\\ -1& n\in \{3,5\}(\mathrm{mod}8)\end{array}$
5. Gauss' law of quadratic reciprocity (1796): If $m$ is odd and $\mathrm{G}\mathrm{C}\mathrm{D}(m,n)=1$ then $\left(\frac{m}{n}\right)=\{\begin{array}{ll}-\left(\frac{n}{m}\right)& m\equiv n\equiv 3(\mathrm{mod}4)\\ \left(\frac{n}{m}\right)& \text{otherwise}\end{array}$

Example

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

$\left(\frac{a}{n}\right)=\left(\frac{n}{a}\right)$ since $n\equiv 3(\mathrm{mod}4)$ but $a\equiv 1(\mathrm{mod}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(\mathrm{mod}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}}(\mathrm{mod}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 [1,n]$ with $a^{n-1}\equiv 1(\mathrm{mod}n)$ AND $a^{\frac{n-1}{q}}\equiv ̸1(\mathrm{mod}n)\mathrm{\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(\mathrm{mod}n)$ and $3^{\frac{617-1}{q}}\equiv ̸1(\mathrm{mod}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.

So a certificate of primality for $n$ consists of

1. an $a$ satisfying the conditions of the theorem
2. a list of all primes $q$ dividing $n-1$
3. Cirtificates fro those $q$.

Verifyingprimality of $n$ takes only $O((\ln n{)}^5)$ bit operations.

Finding certificate could be hard!