Chapter 8 Number Theory262
Primality Testing
It’s easy to see that an integernis prime iff it is not divisible by any number from
2 top
n̆
(see Problem 1.9). Of course this naive way to test ifnis prime takes
more thanp
nsteps, which is exponential in thesizeofnmeasured by the number
of digits in the decimal or binary representation ofn. Through the early 1970’s,
no prime testing procedure was known that would never blow up like this.
In 1974, Volker Strassen invented a simple, fastprobabilistic primality test.
Strassens’s test gives the right answer when applied to any prime number, but
has some probability of giving a wrong answer on a nonprime number. However,
the probability of a wrong answer on any given number is so tiny that relying on
the answer is the best bet you’ll ever make.
Still, the theoretical possibility of a wrong answer was intellectually
bothersome—even if the probability of being wrong was a lot less than the prob-
ability of an undetectable computer hardware error leading to a wrong answer.
Finally in 2002, in a breakthrough paper beginning with a quote from Gauss em-
phasizing the importance and antiquity of primality testing, Manindra Agrawal,
Neeraj Kayal, and Nitin Saxena presented an amazing, thirteen line description of
a polynomial time primality test.
This definitively places primality testing way below the exponential effort ap-
parently needed for SAT and similar problems. The polynomial bound on the
Agrawalet al. test had degree 12, and subsequent research has reduced the de-
gree to 5, but this is still too large to be practical, and probabilistic primality tests
remain the method used in practice today. It’s plausible that the degree bound can
be reduced a bit more, but matching the speed of the known probabilistic tests
remains a daunting challenge.