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...)
On Sat, 5 Mar 2011 14:19:05 +0000 Brent Spillner <spillner@acm.org> wrote:
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. [...]
But explicitly naming the algorithm would preclude replacing its internals with a faster and better algorithm that might come along later. A more generic name means that any code using the function will automatically get the benefit of any improvements to it. is_probably_prime, and a forthcoming is_definitely_prime (once I've had a chance to study the new-to-me algorithm that John Bytheway pointed out), should do pretty much everything anyone needs. -- Chad Nelson Oak Circle Software, Inc. * * *
On 03/05/2011 01:37 PM, Chad Nelson wrote:
But explicitly naming the algorithm would preclude replacing its internals with a faster and better algorithm that might come along later. A more generic name means that any code using the function will automatically get the benefit of any improvements to it.
is_probably_prime, and a forthcoming is_definitely_prime (once I've had a chance to study the new-to-me algorithm that John Bytheway pointed out), should do pretty much everything anyone needs.
More than likely the newer, faster, algorithm will return false positives in some circumstances where the old one would not. How about: template <typename Integral_T> bool is_maybe_prime(Integral_T const &) { return true; // Cf. http://xkcd.com/221/ // return false; // alternatively } I expect most of us would object to this implementation, but the interesting question is how do you justify the objection? If the result of an algorithm is only probabalistically correct, then the really interesting discussions relate to the question of "in what ways does it diverge from the ideal?" and "what are the restrictions on the process which selected the inputs such that the probabalistic estimate remains valid?" Probably most folks who need a function to test very large numbers for primality had better be very familiar the failure modes of the algorithm in use. So the value must be computed with a documented algorithm giving a result about which testable predictions can be made. Otherwise, at the very least, it's difficult to regression test. The algorithm is an essential part of the interface, I think it should be part of the function name (or maybe supplied with template policy tag types?) - Marsh
participants (3)
-
Brent Spillner -
Chad Nelson -
Marsh Ray