What I think is unacceptable is that if a composite passes the test, it also passes the test when invoked a second time because the bases it's tested against are always the same. That's the why of a version that accepts a random state. So, a new function is recommendable in any case. That applies to mpz_millerrabin as well, of course, which is the one actually doing the PRNG calls. And while on that subject, there was also a request for a M-R test function accepting a specific base as parameter: http://gmplib.org/list-archives/gmp-devel/2002-December/000075.html And a suggestion to return the witness that proved the compositeness: http://gmplib.org/list-archives/gmp-devel/2008-January/000766.html In that message, Torbjörn also says that it'd be nice for a function called millerrabin to do a M-R test only, not also a Fermat test.
OK, I hacked something that could be a start for new functions. These are possible function names and interfaces, we might want to change either or both before putting these in GMP. New functions: 1. mpz_pprime_p, for doing some trial dividing and unspecified probabilistic primality tests to specified probability. 2. mpz_notdiv_pprime_p, like mpz_pprime_p but without trial dividing. 3. mpz_millerrabin, replacing the current internal function with the same name (but with different parameters). The new code makes use of redc functions at the mpz level, which I wrote several years ago. (Such functions could also at some point be made part of the public GMP interface.)
pprime_p.c
Description: Binary data
redcify.c
Description: Binary data
redcify.h
Description: Binary data
-- Torbjörn
_______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
