Probable prime tests

Paul Underwood paulunderwood at mindless.com
Thu Apr 19 20:28:47 UTC 2018


The GMP Manual, section 5.9, has the function:

"Function: int mpz_probab_prime_p (const mpz_t n, int reps)

    Determine whether n is prime. Return 2 if n is definitely prime, return 1 if n is probably prime (without being certain), or return 0 if n is definitely non-prime.

    This function performs some trial divisions, then reps Miller-Rabin probabilistic primality tests. A higher reps value will reduce the chances of a non-prime being identified as “probably prime”. A composite number will be identified as a prime with a probability of less than 4^(-reps). Reasonable values of reps are between 15 and 50."

50 repetitions of M-R seems excessive in light of the many Fermat+Lucas tests that exist, for example my own test which is only 5% slower than a Q=1 Lucas test and without a known counterexample: http://arxiv.org/abs/1706.01265

Is there any desire by the authors or users of GMP to have a built-in Lucas or BPSW type test, possible mine? ;-)

Best

Paul


More information about the gmp-discuss mailing list