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