PRIMALITY

MATH 195

Primality Testing

In cryptography, we need to generate large prime numbers. How can we test if a large number is prime?

If n is really prime, then by Fermat’s little theorem, one has

∀a ∈ (ℤ/nℤ)^{∗}, a^{n−1} ≡ 1 (mod n).

If this condition is not satisfied, then we can either be happy anyway or we stumble upon an a ∈ (ℤ/nℤ)^{∗} with a^{n−1} ≢ 1 (mod n) and in that case we output “no”. (If “no”, we can prove that n cannot be prime.)

The resulting probabilistic primality test is called the witness test of Miller and Rabin [see also §7.4 in the text, the Miller-Rabin test].

Suppose that n is an odd prime, a ∈ ℤ. Then n | a^{n} − a (by Fermat’s little theorem), so if we write n − 1 = 2^{k}u (where u is odd, k ≥ 1), we have

n | a(a^{n−1} − 1) = a(a^{(n−1)/2} + 1)(a^{(n−1)/2} − 1)

= a(a^{(n−1)/2} + 1)(a^{(n−1)/4} + 1)(a^{(n−1)/4} − 1)

= ⋯ = a(a^{u} − 1) ∏_{ν=0}^{k−1}(a^{2^{i}u} + 1).

So we have at least one of

a ≡ 0 (mod n)
a^{u} ≡ 1 (mod n)
a^{2^{i}u} ≡ −1 (mod n)

for some i with 0 ≤ i < k.

So now let n be any odd integer > 1 (not necessarily prime) and n − 1 = 2^{k}u where u is odd. If a is an integer satisfying

a ≢ 0 (mod n)
a^{u} ≢ 1 (mod n)
a^{2^{i}u} ≢ −1 (mod n)

for any 0 ≤ i < k, then a is called a witness to the compositeness of n.

So, if a witness to the compositeness of n exists, n is really composite. Though you can be certain n is composite, you cannot extract a divisor (easily) from the proof or algorithm. We do have the following:

This is some of the material covered March 7, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

Theorem. Let n > 1 be an odd integer. If n is prime, then no witnesses for n exist. If n is composite, then

\frac{#\{a : 1 ≤ a ≤ n − 1, a a witness for n\}}{n − 1} ≥ \frac{3}{4}.

Therefore, approximately 75% of congruence classes represent witnesses.

Example. Every one of the numbers 2, 3, 4, 5, 6, 7 is a witness for n = 9, but neither 1 or 8 works. (Since 9 − 1 = 8 = 2^{3}, u = 1, so the conditions are easily satisfied.)

We then have the following algorithm to probabilistically test for primality:

(1) Pick a ∈ {1, …, n − 1} at random, and test whether a is a witness. If yes, output “yes”.

(2) Otherwise, repeat. [Stop after a certain amount of time because probabilistically, n is likely tto be prime, but no mathematical proof.]

Large Primes

Now we can attend to the problem of finding a prime number with a given number of digits. For RSA, we need n = pq with p and q both approximately 150-200 digits.

We have the following naive algorithm:

(1) Pick a random number with k digits.

(2) Test it for primality as above (using the witness test).

(3) Continue until the answer is “yes”.

All algorithms you find will be a variation of this scheme.

Why does this algorithm work? In effect, how often are numbers of size 10^{k} prime? This question is answered by the prime number theorem (proved in 1896) by Hadamard (1865-1963) and de la Valle-Poussin (1866-1962).

Theorem (Prime number theorem).

\frac{#\{p ≤ x : p prime\}}{x} ∼ \frac{1}{log x}

as x → ∞.

This says that the limit of the left-hand side over the right-hand side tends to 1 as x → ∞. “Roughly 1 out of every log x positive integers up to x is a prime number.”

For example, with k = 200, log(10^{200}) ≈ 460, which means the probability that a 200 digit number is prime is 1/460.

By restricting to odd numbers, the probability is twice as large, restricting to numbers not divisible by 3, it is 3/2 times as large, and so on, so we can multiply the probability by

2 · \frac{3}{2} · \frac{5}{4} · · · · · ·\frac{p}{p − 1}

if we eliminate numbers divisible by primes up to p.

The prime number theorem is not easy to prove: D. Newman found an easier proof relying on complex analysis.