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.
Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk