Probable prime tests
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? ;-)
More information about the gmp-discuss