Miller-Rabin
paul zimmermann
Paul.Zimmermann at inria.fr
Mon Mar 26 19:04:06 UTC 2018
Hi,
it would be nice if there would be a GMP function implementing the Miller-Rabin test,
to have finer control than with mpz_probab_prime_p.
This would allow to get a real primality test for small enough input.
For example on https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test we
can read:
if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
thus the GMP user who wants to check inputs less than 4759123141 could write :
int
my_isprime (mpz_t p)
{
assert (mpz_cmp_ui (p, 4759123141UL) < 0);
return mpz_miller_rabin (p, 2) && mpz_miller_rabin (p, 7) && mpz_miller_rabin (p, 61);
}
Alternatively, if you don't want to add a new function, you could allow negative REPS
argument for mpz_probab_prime_p:
* for example REPS=-1 would mean checking base 2 (n < 2,047)
* REPS=-2 would mean checking bases 31 and 73 (n < 9080191)
* REPS=-3 would mean checking bases 2, 7, and 61 (n < 4759123141)
* ...
Paul
More information about the gmp-devel
mailing list