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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.