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,

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

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} n &= 1,209,387 \\ a &= 600,001 \end{align}}

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( \frac{a}{n} \right) = \left( \frac{n}{a} \right)} since 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 \equiv 3 \pmod{4}} but 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 \equiv 1 \pmod{4}}

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( \frac{1,209,387}{600,001} \right) = \left( \frac{9385}{600,001} \right)} by property 1

Apply properties 5 and 1 again...

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( \frac{600,001}{9385} \right) = \left( \frac{8746}{9385} \right)}

Apply property 2...

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( \frac{8746}{9385} \right) = \left( \frac{2}{9385} \right) \, \left( \frac{4373}{9385} \right)}

This becomes 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 1 \cdot \left( \frac{4373}{9385} \right)} by property 4

Apply 5 and 1 two more times...

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( \frac{4373}{9385} \right) = \left( \frac{639}{4373} \right) = \left( \frac{539}{639} \right)}

Now this is the first 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 m \equiv n \equiv 3 \pmod{4}} , so by property 5 and 1,

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( \frac{539}{639} \right) = -\left( \frac{100}{539} \right)}

Note that 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 100 = 2^2 \cdot 25} , so by property 2,

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( \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...

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( \frac{5^2}{539} \right) = -1 \cdot 1 = -1}

This was a lot faster than if we would have tried to compute 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{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

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} is prime iff there is an 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 \in \left[1, n \right]} 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 a^{n-1} \equiv 1 \pmod{n}} 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 a^{\frac{n-1}{q}} \not\equiv 1 \pmod{n} \quad \forall q \mid (n-1)} , where 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 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

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 = 617}

Hint: this tree is the short certificate

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

For 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 = 617} , 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 = 3} works! In other words, 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 3^{617-1} \equiv 1 \pmod{n}} 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 3^{\frac{617-1}{q}} \not\equiv 1 \pmod{n}} for all 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 q \mid (n-1)} . These 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 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 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} consists of

1. an 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} satisfying the conditions of the theorem
2. a list of all primes 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 q} dividing 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-1}
3. Cirtificates fro those 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 q} .

Verifyingprimality 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} takes only 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 O((\ln{n})^5)} bit operations.

Finding certificate could be hard!