On 8/4/11 9:32 AM, Jerome Baum wrote: > So just a sieve? Isn't that going to take ages on any reasonable key? No. http://en.wikipedia.org/wiki/AKS_primality_test