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

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Brent Spillner (spillner_at_[hidden])
Date: 2011-03-05 09:19:05

On 4 Mar 2011 at 21:57. Christopher Jefferson wrote:
>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.

I'd vote for "rabin_miller_pseudoprime()"... those familiar with
number theory will understand exactly what it does, and you can add
the number of iterations as a parameter with a sensible default value.
 Other users will at least recognize that it's not quite the same
thing as a deterministic primality test, and if they look up the term
'pseudoprime' they'll find plenty of primer material on the subject.

At any rate, this is /not/ just a philosophical debate-- there are
known attacks that pass pseudoprimes to weak testing functions, and an
unsophisticated user who finds a nondeterministic is_prime() function
in a library is likely to write susceptible code.  (cf.
http://webcache.googleusercontent.com/search?q=cache:CPnKD-Rq1X4J:www.iacr.org/archive/pkc2005/33860010/33860010.ps)