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

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.