Fastest Primality Test?

Date: 12/21/2005 at 17:02:19
From: Norbert
Subject: Polynom prime factorization

Hello!  I would like to ask about "the fastest prime test".  I found
an interesting article on the Internet which said, "We present a
deterministic polynomial-time algorithm that determines whether an
input number n is prime or composite."  It was from the Department of
Computer Science and Engineering at the Indian Institute of Technology
in Kanpur, India.  I have some questions about it:

  1. Is it really faster than the Rabin Miller or Lucas tests?

  2. If it is true, why can't we use this form to search prime numbers 
with distributed algorithm? (e.g www.mersenne.org, Mersenne-Prime)?

  3. The algorithm speed is O(log^12 N).  What do you think about this 
algorithm?  Could the mathematicians develop an algorithm about 
O(log N)? 

Thank you.

- Norbert

Date: 12/22/2005 at 20:25:20
From: Doctor Vogler
Subject: Re: Polynom prime factorization

Hi Norbert,

Thanks for writing to Dr. Math.  Those are very good questions.  

First of all, the Rabin-Miller test is a pseudo-primality test, which
means that if you give it a composite number, then it will _probably_
tell you that it is composite.  But if you give it a prime number,
then it will tell you that it is _probably prime_.  A composite number
that passes a pseudoprimality test is called a pseudoprime.  It turns
out that it is not known whether there are any Rabin-Miller
pseudoprimes, but no one has yet proven that there are none.  

There are other primality tests that are more efficient than the
algorithm you just mentioned, in the sense that they finish more
quickly on numbers that we've tried, but they are _probabilistic_
algorithms, which means that some part of the algorithm is based on
choosing a random number and then doing some computations with it. 
With a certain probability, it will tell you that your number is
either prime or composite.  In practice, after a few tries, you get a
result.  

But many mathematicians wanted to find a _deterministic_ algorithm
(one that is guaranteed to finish in no more than a known number of
steps) which will (provably) finish in a number of steps that is a
polynomial in log N.  That is what this new algorithm does, and the
creators proved that it would always finish in O((log N)^12) time. 
Later, someone else proved that it would, in fact, finish more quickly
than that, in almost O((log N)^6) time.  That still doesn't make it
faster than other tests, though, just faster than other general-
purpose deterministic primality tests.

The Lucas-Lehmer primality test is a deterministic primality test, but
it is not general-purpose because it only works on Mersenne numbers. 
It is much faster than other algorithms (such as the one you
mentioned), but it only works for those special numbers.  Consider
that mersenne.org reports that the 42'nd Mersenne prime found was

  N = 2^25,964,951 - 1,

which took 50 days on a 2.4 GHz computer, which is

  50 days * 24 hours/day * 60 minutes/hour * 60 seconds/minute
      * 2,400,000,000 instructions/second

   = 10,368,000,000,000,000 instructions

(or, more correctly, cycles, but the difference is not important).  In
this case,

  log N = 25,964,951 * log 2
        = 17,997,532.58...

and

  (log N)^12 = 1,154,929,888,777,235,354,042,315,422,387,627,895,434,
     164,939,766,318,268,467,306,355,354,201,088,395,258,493,601,391

which is a whole heck of a lot more than the number of instructions
used in the Lucas-Lehmer test.  In fact,

  (log N)^6 = 
        33,984,259,426,640,965,925,133,186,173,883,788,875,047,677

which is still a heck of a lot more.  How many days would this many
instructions take on that 2.4 GHz computer?  How many trillions of years?

See also the MathWorld sites on

  Primality Test
    http://mathworld.wolfram.com/PrimalityTest.html 

  Rabin-Miller Strong Pseudoprime Test
  <http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

  Lucas-Lehmer Test
    http://mathworld.wolfram.com/Lucas-LehmerTest.html 

  AKS Primality Test
    http://mathworld.wolfram.com/AKSPrimalityTest.html 

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/