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

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Christopher Jefferson (chris_at_[hidden])
Date: 2011-03-04 16:57:24

On 4 Mar 2011, at 21:45, Artyom wrote:

> 
> 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.

The problem is that there might well be small numbers which always return the correct value (it is hard to know).

As a point of information, the GAP system (a mathematical computation system I use) calls its primality function " isProbablyPrime".

Mathematica just says "PrimeQ", but they make the claim that they have done extensive mathematical and practical testing, and never found a number which their probabilistic algorithm fails on.

Unless someone is willing to put that amount of work in, I personally would much prefer is_probably_prime.

> 
> It is all matter of measure and interest. Anybody who works with prime
> numbers for cryptography is aware of probabilistic testing.

But people who are just writing some basic mathematics code might not. If their programs fail one run out of a million, I would consider that a bug.

> 
> 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.

But if we found a bug, we would fix it ;)

Chris