Miller-Rabin

[paul zimmermann]

       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