3/19 15-682 Randomized Algorithms
Randomized algorithms for number-theoretic problems.
Today: Randomized algorithms for testing primality.
==============================================================================
First, in all the algorithms we will assume that n is odd, not a prime
power, and not a perfect square. (These are fine to assume since we
can always begin by checking if the square-root, cube-root, etc. of n
is an integer, and if so saying "composite".)
Here's a BPP algorithm for primality testing. This one is probably the
easiest to analyze, and I think is due to Lehmer.
Repeat k times:
* Pick a in {1,...,n-1} at random.
* If gcd(a,n) != 1, then output COMPOSITE.
[this is actually unnecessary but conceptually helps]
* If a^{(n-1)/2} is not congruent to +1 or -1 (mod n),
then output COMPOSITE.
Now, if we ever got a "-1" above output "PROBABLY PRIME" else output
"PROBABLY COMPOSITE".
Theorem: this procedure has error probability at most 1/2^k.
Proof: if n is really prime, then in each iteration we get
a^{(n-1)/2} = -1 (mod n) with probability 1/2, so we get a -1 at least
once with probability 1 - 1/2^k. If n is composite, the proof of
success will follow from the lemma below with t = (n-1)/2.
Key Lemma: Let n be an odd composite, not a prime power, and let t <
n. If there exists a in Z_n^* such that a^t = -1 (mod n), then at
most half of the x's in Z_n^* have x^t = {-1,+1} (mod n). In fact, we
can weaken the condition to simply that there exists a in Z_n^* such
that a^t is not congruent to +1 (mod n).
Proof: Let S = {x in Z_n^* : x^t = +1 or -1 (mod n)}. S is a subgroup
of Z_n^* since it's closed under multiplication (xy)^t = (x^t)(y^t)
and inverse (x^{-1})^t = (x^t)^{-1}. So we just need to find some b
in Z_n^* not in S. (So, the "weakened condition" is equivalent to the
stronger condition because if a^t is not congruent to -1 (mod n), then
we're done.) Let n = q * r, where q and r are relatively prime
and greater than 1. Let b = (a,1), where we're using CRT notation:
b = a (mod q) and b = 1 (mod r). Note that b^t = (a^t, 1^t) = (-1,1).
Therefore, b is not in S since 1 = (1,1) and -1 = (-1, -1). QED.
========================================================================
An aside: it's clear that primality is in co-NP: if a number is
composite, there is a short witness: namely, a factor. Is primality
in NP? Yes. Here's an idea due to Pratt:
The certificate that n is prime will be a generator g of Z_n^*, a
prime factorization of n-1, and then (recursively) a proof
that each of those prime factors is really prime.
The idea is that if n is prime, then g^{n-1} = 1 (mod n) and g^t is
not congruent to 1 (mod n) for any 0 < t < n-1. On the other hand, if
n is composite, then phi(n) < n-1 so this cannot be the case. So, to
verify that n is prime, we just verify that g^{n-1} = 1 (mod n) and
then verify that g^{(n-1)/p} is not congruent to 1 for any prime
factor p of n, and then recursively verify that each of these factors
is prime (and, of course, verify that the prime factorization really
is a factorization of n). We can see that this certificate is not too
large since if you draw out the recursive "tree", the width is at most
log(n) (since the product of all primes on any given level is at most n)
and the depth is at most log(n) since the primes are dropping by at
least a factor or 2. QED.
===========================================================================
We now turn to an RP algorithm for compositeness, the Solovay-Strassen
algorithm. First, we need to define a generalization of the Legendre
symbol called the Jacobi symbol:
If n = p1 * p2 * ... * pt, where the pi are primes not nec. distinct,
[a/n] = [a/p1]*[a/p2]*...*[a/pt].
It turns out that the Jacobi symbol can be calculated efficiently
(essentially using a Euclidean GCD-like algorithm) via a number of
identities that are not trivial to prove. A couple easy-to-prove
identities are: [ab/n] = [a/n]*[b/n], and if a=b (mod n) then [a/n]=[b/n].
Here is the Solovay-Strassen algorithm:
* Pick random a in {1,...,n-1}
* if gcd(a,n) != 1, then COMPOSITE.
* if [a/n] != a^{(n-1)/2} then COMPOSITE.
* else say POSSIBLY PRIME.
Thm: if n is composite, then this algorithm says "composite" with
probability at least 1/2.
Proof: the proof is much like that of our "key lemma".
Let J = {a in Z_n^* : [a/n] = a^{(n-1)/2} (mod n)}.
J is a group (e.g., use fact that [ab/n] = [a/n]*[b/n]) so it suffices
to show there exists b not in J. By the assumption that n is not a
prime power and is not a perfect square, we can write n = p1^e1 * r,
where p1 and r are realatively prime, and e1 is odd. Let g be an
arbitrary non-residue mod p1, and let b = (g,1), in CRT notation. We
can see that b^{(n-1)/2} = (g^{(n-1)/2}, 1) is *not* congruent to -1
(mod n), since -1 = (-1, -1). So, it suffices to show that [b/n] = -1.
This in turn follows from the basic Jacobi symbol identities:
[b/n] = ([b/p1])^e1 * [b/r] = ([g/p1])^e1 * [1/r] = (-1)^e1 * 1 = -1.
QED
========================================================================
We now describe one final RP alg for compositeness. This is along the
lines of using a^{n-1} =? 1 (mod n) as a test.
Miller-Rabin Algorithm:
* Let n = 2^r * B, where B is odd.
* pick a in {1,...,n-1} at random.
* Compute a^B, a^{2B}, ..., a^{n-1} (mod n).
* If a^{n-1} != 1 (mod n), then output COMPOSITE
* If we found a non {-1,+1} root of 1 in the above list, then
output COMPOSITE.
* else output POSSIBLY PRIME.
Note that we only have to worry about Carmichael numbers (composite n
such that all a in Z_n^* satisfy a^{n-1} = 1 (mod n)). For all other
composite numbers, at least half of the a's don't have this property
(since {a : a^{n-1} = 1 (mod n)} is a group).
Here's how we can argue for Carmichael numbers:
Suppose there exists a in Z_n^* satisfying a^{(n-1)/2} != 1 (mod n).
Then our "Key Lemma" implies that with probability at least 1/2, we
will find a non {-1,+1} root of 1 in computing a^{(n-1)/2} and output
COMPOSITE. If no such a exists, but there exists b in Z_n^* such that
b^{(n-1)/4} != 1 (mod n) then similarly we're OK (assuming n-1 is
divisible by 4). Going down the line from right-to-left, we can now
assume w.l.o.g. that all a in z_n^* satisfy a^B = 1 (mod n).
We now show a contradiction: let n=p1^e1 * r, where e1 is odd and p1
and r are relatively prime. Let g be a generator mod p1^e1 (we didn't
prove it, but the prime power groups are cyclic too; actually,
Carmichael numbers must be products of distinct primes, but we didn't
prove that either). Let a = (g,1) using CRT notation. If a^B = 1 (mod n)
then g^B = 1 (mod p1^e1), which means that B must be a multiple of
phi(p1^e1) since g is a generator. But B is odd and phi(p1^e1) is
even, a contradiction. QED