Miller-Rabin

[Niels Möller]

paul zimmermann <Paul.Zimmermann at inria.fr> writes:

> 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.

There's an internal function mpz_millerrabin, but it also takes a reps
argument, not a base.

  int
  mpz_millerrabin (mpz_srcptr n, int reps);

(And it also starts with a (supposedly?) faster Fermat test).

If it is made public, it would be the right choice for use cases where
small prime factors are very unlikeky, so that it isn't worth the effort
to start with any trial division.

If we want to let the caller provide the base, there are some
preparations that it would be nice to not repeat for each base (even if
the computational cost is close to negligible, so this is mostly
aestethics ). So maybe it would be better to provide a list of bases,
something like

  int
  mpz_miller_rabin_uis (mpz_srcptr n, size_t count, unsigned long *bases);

Or would this be useful to do this also with a bignum base? (Small or
large base should have only a marginal effect on the computational cost,
since most of the powm will work with numbers of the same size of n, so
this is more a question of what's useful and what the interface should
be like).

> 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;

Out of curiosity, are any similar results known when using bases given
by Euler's polynomial,

  a_j = j^2 + j + 41, 

with the curious property that j_40 = 41^2 is the first composite in the sequence?

We might have discussed that earlier, when using that sequence of bases
in mini-gmp's probably prime test.

> 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)
> * ...

I think that's a bit too obscure for the interface.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.