View Full Version : Primality testing *is* in P - Proof

August 6th, 2002, 23:10
For those who understand the topic:


August 12th, 2002, 12:39
Interesting... the algo is really simple.
But unfortunately this is not of great use for us crypto freaks since randomized algos are faster on the number we use but this will help a lot the guys who are looking for the biggest primes

August 17th, 2002, 14:15
I wonder why you say that Thigo?

From my understanding it should give a higher probability of determining if a number is a prime so you can allways start with using the allready existing algorithms and then end it off with this one. I think it's useful for any use to give more accurate results but maybe you can give a reason why you think otherwise?

I'm allready waiting to see first pratical implementations but maybe thats too soon yet.

// CyberHeg

September 11th, 2002, 07:07
I still like probablistic algorithms because if you run them for 20 or so iterations (assuming CPU cycles are cheap these days), an error of 1/(2^1000000) is so close to zero, it might as well be zero The ECPP test is one such test that works like this, but I'm very interested in the new polytime algorithm by Agrawal, Kayal and Saxena (the authors of the paper from the first post).

Their result lies on using Fermat's Little Theorem. A quick rundown of the proof is at