Re: [boost] [xint] Boost.XInt formal review

Subject: Re: [boost] [xint] Boost.XInt formal review
From: John Bytheway (jbytheway+boost_at_[hidden])
Date: 2011-03-04 15:01:38

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