Turns out, Primes are in P

zorba1 writes "Manindra Agrawal et. al. of the Indian Institute of Technology Kanpur CS department have released a most interesting paper today. It presents an algorithm that determines whether a number is prime or not in polynomial time. While I haven't gone through the presentation in detail, it looks like a promising, albeit non-optimized, solution for the famous PRIMES in P problem."

Comments

What is 'x' and how is 'q' calculated?

[Mr. Sketch]

From looking at the algo, I can't figure out what 'x' (or maybe it's a chi) is? Can someone help? I've looked it over, but couldn't find a definition of it. I'm also assuming that the 'if (r is prime)' line is a recursive call to itself? Also, how do we determine 'q' the 'largest prime factor of r-1' ? Another recursive call to get the factors? I must admit, I'm kind of lost by the algo, but it's still interesting.

O(num_bits**12) time estimates

[Adam J. Richter]

We give a deterministic O((log n)**12) time algorithm for testing whether a number is prime.

[Sorry, the Slashdot filter does not allow me to superscript the 12.]

The algorithm takes O(log2(n)**12) time, where n is number being factored. If we optimistically assume that this algorithm can test the primality of a 16-bit number in one microsecond, then here is how long it would take to test time primality of some larger numbers.

• 2**12 times as long for a 32-bit number = 4096 microseconds = 4 milliseconds,
• 4**12 times as long for a 64-bit number = 16,777,216 microseconds = 16 seconds,
• 8**12 times as long for a 128-bit number = 68,719,476,736 microseconds = 68,719 seconds = 19 hours,
• 16**12 times as long for a 256-bit number = 281,474,976,710,656 microseconds = 9 years.

I don't know what a realistic base time for this algorithm really would be, and I don't know where the cross over point against existing exponential time deterministic primality testing algorithms would be, but at least this provide a sense of how log2(n)**12 grows.