On Fri, 04 Mar 2011 20:01:38 +0000 John Bytheway <jbytheway+boost@gmail.com> wrote:
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.
I stand corrected. I hadn't heard about that test, and I was under the impression from my study of the field, a few years earlier, that most mathematicians didn't expect to ever find one. Thanks for pointing it out, I'll be very interested to see how it works, and exactly how much slower it is.
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.
When probably-prime algorithms were the only known ones, calling it is_prime was justifiable. Given the existence of a true primality test, it's not. I'll change it for the next iteration. -- Chad Nelson Oak Circle Software, Inc. * * *