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

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Artyom (artyomtnk_at_[hidden])
Date: 2011-03-04 16:45:57

----- Original Message ----
> From: John Bytheway <jbytheway+boost_at_[hidden]>
> 
> 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