On 04/03/11 14:29, Chad Nelson wrote: <snip>
I'm only an amateur cryptographer, but it's generally understood in the field that it is impossible to prove that something is truly prime without actually factoring it. In saying that a number "is prime," there's always an unspoken "with a high degree of certainty" attached.
That's not true. There is a polynomial-time primality testing algorithm: http://en.wikipedia.org/wiki/AKS_primality_test whereas there is no known polynomial time factorization algorithm. Of course, it's true that no one uses AKS in practice because it's still far slower than Miller–Rabin, and non-prime-with-sufficiently-small-probability is good enough for all crypt applications. Even so, I would name the function is_probably_prime. If you call it is_prime then I at least, and perhaps others, would guess it implements a slower algorithm like AKS, and I would worry if I saw code using it because it might be slow. John