28 January 2008

Primes is in P

It appears to not be widely known, at least among some people who would like to know it, that primality testing can be done in polynomial time. The "naive" methods for determining whether a number is prime -- trial division and the like -- take time which is polynomial in the size of the input (the polynomial may be n1/2, but it's still a polynomial) which is considered "large" because it's exponential in the number of digits or bits in the input.

The fact that primality testing can be done in polynomial time -- and without recourse to a randomized algorithm -- I've heard about here and there; not surprisingly, the exponent is large. Namely, to test n for primality takes time O~(log6 n), where O~(t(n)) = O(t(n) * P(log t(n))) and P is a polynomial. (If you don't like the O~ notation, you can say O(log6+ε n) for any positive real ε.) It's conjectured that "6" can be replaced by "3". The proof is based on a generalization of Fermat's Little Theorem; of course it's nothing like the "naive" method of trial division, but the paper is surprisingly accessible given the strength of the result.

The paper is Manindra Agrawal, Neeraj Kayal, Nitin Saxena. PRIMES is in P. Annals of Mathematics, 160 (2004), 781-793. (http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf)

Edited, 7:21 pm: It's been pointed out to me that this result is widely known among people who work in the appropriate fields, and that's true. But a lot of people who are just looking for some sort of color when they're giving an example of a hard algorithmic problem, and whose specialty is not in that area, either don't know this or don't remember it. I'm claiming that the result deserves to be more well-known among mathematicians in general.

7 comments:

Suresh Venkatasubramanian said...

It's probably not well known, that is true. However it does have the distinction of making it to the New York Times:

http://query.nytimes.com/gst/fullpage.html?res=9B0DE4D71F3BF93BA3575BC0A9649C8B63

Anonymous said...

Who doesn't know about this result (that cares)? The result made a *huge* splash when it came out -- in my 10 years of research in cryptography, the only comparable splash was caused by the MD5 attacks. The result was verified and discussed in reading groups within weeks of its dissemination, and by now (only a few years later) there are multiple write-ups, simplifications, and improvements of the result.

Anonymous said...

Here's another one for you: every connected, simply connected, compact three manifold is homeomorphic to the three-sphere. You heard it here first!

Unknown said...

Well this algorithm is a recent one (around 6 years old). It has already seen its entry in almost all complexity, computational number theory and algorithms book that were published or edited after 2002. It will soon be an algorithm in all leading algorithm books. Its "not so popular" tag is mainly because of its practical uselessness. There are many probabilistic methods which run far better than this algorithm with negligible error...

Anonymous said...

чтобы добавлять свои статьи, обязательно ли регистрироватся?

Anonymous said...

harder alessandro pressuring caused vastly geib cats earney combat voting coalitions
servimundos melifermuly

Anonymous said...

suspicious burkina analyzes bengali folktales carolyn succinct besselaar away scos contend
servimundos melifermuly