Notes on primality testing

In order to use the RSA algorithm or other related cryptosystems effectively,
it is necessary to generate large prime numbers.

Formal proofs that very large (say 100 digit) numbers are prime are not easy
to come by.  However, there are tests which will allow one to conclude with
an arbitrarily high degree of probability that a randomly chosen 100
digit number is prime (or that it isn't).  Furthermore, the probability
that a randomly chosen 100 digit number is prime is high enough that it
is worth searching for primes in this way.

Prime Number Theorem:  the number of primes less than N is approximately
N/ln(N).

This means that a randomly chosen number less than N has a probability of
about 1/ln(N) of being a prime.  If N is 10^100, for example, ln(N) is 
(very) approximatly 200, so about 1 in 200 of numbers less than 10^100
(or 1 percent of odd numbers less than 10^100) will be prime.

We need to develop some theory.

First, we need a fact about multiplication mod p, where p is prime:
for any prime p, there is a positive x < p such that x^(p-1) = 1
(this is always true because p-1 = phi(p)) but x^b is not 1 for any
b < p-1.

This can be proved by a counting argument.  Such an x is called a
"primitive root" mod p.  There are phi(p-1) primitive roots mod p.

(I can present the proof that there is at least one primitive root
from the book).

1.  if a has order l (l is the minimum number such that a^l = 1 mod
p-1) and b has order k, and gcd(k,l) = 1, then ab has order kl.
Certainly ab^kl = 1.  It follows that the order of ab must be a
divisor of kl.  If ab^e = 1, then a^e and b^e are reciprocals.  It is
easy to see that reciprocals have the same order.  But the only powers
of a and b that can have the same order are the powers equal to 1,
because k and l are relatively prime (the order of a^e must be a
divisor of l, and the order of b^e must be a divisor of k, and the
only common divisor is 1, so a^e = b^e = 1).

2.  Now let q be a prime divisor of p-1 and let q^n be the largest
power of q which is a divisor of p-1.  We show that there is a residue
class mod p of order q^n.

There can be no more than q^n "q^nth roots of unity mod p" by the
usual considerations -- for any exponent d, there can be no more than
d dth roots of 1 for familiar algebraic reasons.  Note that this is
not true mod n when n is not prime -- for example, every odd number is
a square root of 1 mod 8.  Look at the proof to see why (ab = 0
implies a = 0 or b = 0 plays an essential role).  Algebra mod p is
especially well-behaved because every residue class has a reciprocal
and there are no "zero divisors" except 0 itself.

An element of order q^n will be a q^nth root of unity which is not
also a q^(n-1)th root of unity (notice that the order of any q^nth
root of unity has to be a divisor of q^n and so a power of q).

Thus, if we can show that there are _exactly_ q^n q^nth roots of unity
mod p, it follows that there are at least q^n-q^(n-1) elements of order
q^n, because there can be no more than q^(n-1) q^(n-1)th roots of unity.

Review the factorization x^k-1 = (x-1)(1+x+...+x^(k-1)).

Prove that a polynomial of degree n can have no more than
n roots -- if a is a root of P(x) = 0,
then we have P(x)-P(a) = 0 as well, and P(x)-P(a) has x-a
as a factor (because x^n-a^n always has x-a as a factor).
We need to do the proof with care because we have to be able
to see that it works in the unfamiliar mod p environment.

Consider the dth roots of unity where d is any factor of p-1.
x^(p-1) = 0 has p-1 roots -- every residue mod p other than 0 satisfies
this because p-1 = phi(p).  Now p-1 = de.  x^(p-1) - 1 =
(x^d)^e - 1 = (x^d-1)(x^d+x^(2d)+...+x^(e-1)d)  The right hand factor
has no more than d(e-1) = (p-1)-d roots because of its degree.
The left hand factor has no more than d roots because of its
degree.  But the total number of roots must be p-1, so x^d-1
must have exactly d roots (and the other polynomial must have
exactly (p-1)-d roots). 

Let d = q^n and we see that there must be an element of order q^n.

Now for each prime factor q and maximal power q^n dividing p-1
we can find an element of this order, and multiplying all these
elements together we find that the order of their product is the
product of their orders (because the orders are relatively prime)
so the order of the product must be p-1 which is what we wanted.

There is a different way to do this proof:

1.  prove that if order of a is k and order of b is n and gcd(k,n)=1
then order of ab is kn (as above).

2.  observe that if a is an element of order k and n is a divisor of k,
then there is an element of order n:  a^(k/n) works. 

3.  Given an element a of order k and an element b of order n,
it is then always possible to construct an element of order
the least common multiple (lcm) of k and n.  Observe that there
will be an element c of order l/gcd(k,l).  It then follows, because
k and n/gcd(k,n) are relatively prime, that ac will be an element
of order kn/gcd(k,n) = lcm(k,n).

4.  It is then clear that it is possible to construct an element whose
order is the least common multiple of _all_ orders of nonzero numbers
mod p.  Now suppose that this least common multiple (call it m) were
less than p-1.  It would follow that every nonzero residue mod p
is an mth root of 1 (since its order is a divisor of m).  But there
can be no more than m mth roots of unity mod p, which is impossible
if m < p-1.

Definition: Suppose p is an odd prime.  We call a positive x<p a
"quadratic residue mod p" just in case y^2 = x mod p for some y (a
quadratic residue mod p is a "perfect square" mod p).

note that if x^2 = y^2 mod p, we have (x-y)(x+y) = 0 mod p,
so either x = y mod p or x = -y mod p (this relies on p being prime!)

Give the counterexample of mod 8, where 1,3,5,7 are all square roots of 1.

There are thus exactly (p-1)/2 quadratic residues:  there are (p-1)/2 pairs
of "additive inverses" mod p, each associated with a different square.

Theorem:  If p is an odd prime, x is a quadratic residue mod p
iff x^((p-1)/2) = 1 mod p.

One side of this is easy.  If x = y^2 mod p then x^((p-1)/2) =
y^(p-1) = y^phi(p) = 1 by a theorem we have already proved.

The other side goes as follows:  let b be a primitive root mod p.
x = b^i for some x.  If x^((p-1)/2) = 1 mod p, then 
b^i(p-1)/2 = 1 mod p, so i must be even and x is the square of
b^(i/2).

If p is an odd prime, we make the following

Definition:  (a/p) = 0 if a is divisible by p, 1 if a is a quadratic
residue mod p, -1 otherwise.

where p is prime, (a/p) = a^((p-1)/2) mod p.

Gauss's Lemma: Where P = (p-1)/2, consider the multiples a, 2a,
3a,...,Pa, where a is not a multiple of p.  Each of these will be
equal mod p to a unique nonzero number strictly between -P and P.  Let
m be the number of these which are negative.

The multiples will be of the form +n or -n for each n from 1 to P.
No two of them will have the same absolute value, or we would
have ma + na = 0 mod p with m+n <= p-1 -- a would be a factor of
p which is impossible.

So the product a(2a)...(Pa) is equal to (+-1)(+-2)...(+-P)

Factor out P! from both sides and we have a^P = the product of the
signs of the multiples of a thus reduced.  This means that if an odd
number of the reduced multiples of a are negative, (a/p) is -1, and if
an even number of the reduced multiples of a are negative, (a/p) is 1.
It is equivalent to look at the residue classes of multiples of a
computed in the usual way and count the number of residue classes
greater than P.

We extend this notation to define (a/n) where n is odd but not
necessarily prime: the idea is that (a/p) is defined as above, and
(a/mn) is defined as (a/m)(a/n).  Given the prime factorization of
n, it is easy to compute (a/n), which is called the "Jacobi symbol";
it turns out that it is possible to compute the Jacobi symbol efficiently
without knowing the prime factorization of n at all!

We see this via a series of lemmas:

Lemma 0: if a = b mod n, (a/n) = (b/n) -- this is obvious, since (a/n)
depends only on the residue class mod n that a belongs to.

Lemma 1:  (2/n) = 1 if n = 1 or -1 mod 8. and -1 if n = 3 or -3 mod 8.

It is not hard to see that this will be true for all n if it is true
for n = a prime p.  (count factors of 3 mod 8 -- observe that 3*3 = 1
mod 8).

Proof:  We apply Gauss's lemma.  Consider the multiples
2, 2*2, 3*2, etc. up to P*2.  We need to count the number of these
which turn out to be "negative":  it is easy to see (because 2*P = p-1 < p)
that the "negative" ones are exactly those that belong to residue classes
greater than P computed in the usual way.

Let n = 8k + r, where r = 1,3,5, or 7.  We need to count integer
solutions of the inequality n/2 < 2a < n, or, equivalently, (8k+r)/2 <
2a < 8k+r, equivalently 2k+r/4 < a < 4k+r/2, or r/4 < a < 2k+r/2.  Now
observe that between r/2 and 2k+r/2 there are an even number of
integers, so removing the 2k while it may change the number of
solutions, will not change the parity (even-ness or odd-ness) of the
number of solutions, which is all we care about.  So we can count the
number of solutions of r/4 < a < r/2.  For r = 1, there are no
solutions.  For r = 3 and r = 5, there is one solution.  For r = 7,
there are two solutions.  This means that if n=1 or if n = 7 = -1 mod
8, (2/n) = 1, while if n = 3 or n = 5 = -3 mod 8, (2/n) = -1,
by Gauss's lemma.

Lemma 2:  (ab/n) = (a/n)(b/n)  Clearly follows if it is true
when n is prime.  The product of two perfect squares mod p
is certainly a perfect square mod p.  The product of a perfect
square and a non-square cannot be a square -- if a^2n = b^2
then (b/a)^2 = n.  The argument that the product of two non-squares
must be a square is a counting argument -- let q be a non-square --
multiplication by half of the non-zero residues (the squares)
yields non-squares, so multiplication by the other half(the non-squares)
must yield squares.

Lemma 3:  when m and n are odd, (m/n) = -(n/m) if m =n = 3 mod 4
and (n/m) otherwise.

This is a generalized version of a famous theorem of number theory,
the "law of quadratic reciprocity" first proved by Gauss.  I'm not going
to prove it; if anyone in the class is curious, I may post notes about
how to do it.  The flavor of the proof is similar to that of the proof
of Lemma 1 above, but the proof is more complicated.

With the aid of these lemmas, (a/n) can be efficiently computed without
knowing the factorization of n!

(do examples)

We care about this for the following reason:

1.  if n is prime, then for every integer a in [1,n-1], we have
(a/n) = a^((n-1)/2)  (by theorem proved above)

2.  if n is composite, this is true for at most half of a < in [1,n-1].

A proof is outlined in exercise 4.14.  Mathematically inclined
students are invited to try to work their way through this argument;
credit can be earned in this way (if you choose to work on this and
have trouble with some part of the proof, don't hesitate to ask me for
help).

This justifies the following probabilistic algorithm (the Solovay-Strassen
primality test).

To determine whether n is prime:

choose a random number a between 1 and n-1.  Compute a^((n-1)/2).

if you get (a/n), conclude that n is prime.

if you get -(a/n), conclude that n is composite.

The probability of error (in case n is actually composite) is less than or
equal to 1/2.  Of course, if n is prime, the correct answer will be given.
If the test says that n is composite, n is really composite.  

If this test reports that n is prime 50 times, the probability that
n is composite is less than or equal to 1/(2^50) (very small!).

The test can be carried out efficiently because of the fact that we
can compute Jacobi symbols (a/n) without knowing anything about prime
factorizations.