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

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Chad Nelson (chad.thecomfychair_at_[hidden])
Date: 2011-03-05 14:24:05

On Fri, 04 Mar 2011 20:01:38 +0000
John Bytheway <jbytheway+boost_at_[hidden]> 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.
*
*
*