Probabilistic primality tests faster than Miller Rabin?

[CRGreathouse]

Interesting, could I have citations (or at least titles) for Chen/Greene, Menezes, and ISPEC 2005? I'm not having much luck with Google.

[danaj]

Chen/Greene:
http://www.d.umn.edu/~jgreene/papers...ie_PSW_Fib.pdf
I thought they had some slide sets as well, but I don't see them.
Grantham has some nice slides from a couple "SERMON" conferences describing his searches for "reduced sets for likely solutions to the $620 problem".

Menezes: http://cacr.uwaterloo.ca/hac/

Park ISPEC: http://dx.doi.org/10.1007/978-3-540-31979-5_7

[mathPuzzles]

danaj, thanks very much for your detailed followups. Those are very much what I had in mind, and match my own thoughts. But you even give references to follow, which is beyond the call of duty!

From this discussion I see that the task of probable prime TESTING is pretty straightforward (trial divisions, then MR) but the lively discussion of primality PROVING was a more open topic, and depends quite a bit on the number range and packages used. Thanks everyone for teaching me that "AKS=theoretically nice, practically poor".

[CRGreathouse]

Originally Posted by mathPuzzles

Thanks everyone for teaching me that "AKS=theoretically nice, practically poor".

I should note that this is a big improvement from the original version, in which AKS was a galactic algorithm, nearly impossible to run. Thanks to a fair number of improvements from a large number of mathematicians, it's 'merely' millions-to-billions of times slower than the competition -- ok, that still probably qualifies as galactic, but the exponent was reduced by a factor of 3 and Bernstein knocked off a massive constant factor, pretty impressive if you ask me. We're not quite at the point that one more such discovery would make AKS practical but it's not completely crazy to think about it happening.