For those who understand the topic:

h**p://www.cse.iitk.ac.in/primality.pdf

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

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

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

h**p://w*w.utm.edu/research/primes/prove/prove4_3.ht*l