----- Original Message ----
From: John Bytheway <jbytheway+boost@gmail.com>
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.
That is very interesting and important from theoretical point of view but is not practical from any other.
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.
I'm sorry but: Does is_prime fails with probability lower then probability: a) That a bit become accidentally flipped in the CPU or RAM in this test giving wrong result? b) That earthquake is going to smash the entire building and destroy the computer next second. c) That a hacker controls the computer and changes this random bit. It is all matter of measure and interest. Anybody who works with prime numbers for cryptography is aware of probabilistic testing. I think that renaming "is_prime" to "is_probably_prime" is same as renaming the code "this_code_is_bug_free" to "this_code_is_probably_bug_free" and we both know that the second case has much higher probability to fail then the first one. Just to give some perspective. Artyom