mpz_millerrabin

[Torbjorn Granlund]

[I wrote a reply to this within some hours, but somehow lost it.  I
noticed that fact from the archives.  Sorry for the late reply!]

nisse at lysator.liu.se (Niels Möller) writes:

  The function mpz_millerrabin seems to be undocumented and marked as
  "internal". I want to test primality for numbers where I already know
  that there are no small factors, so I'd like to avoid the trial
  division work done by mpz_probably_prime_p.
  
  I'm considering simply writing a configure check for the
  mpz_millerrabin function, and use it if it is available. I have
  difficulty imagining any useful changes to the current interface of
  this function,
  
    int
    mpz_millerrabin (mpz_srcptr n, int reps)
  
  (The interface for mpz_probab_prime_p, on the other hand, is somewhat
  fishy, and I think we have been discussing replacing the repetition
  argument, which makes sense only if you know the final test is
  millerrabin, with some bound for the probability of error).
  
  Another alternative would be to copy GMP's current miller-rabin
  function, or write my own, to ensure that it's always available, but
  that seems like a waste of time.
  
The pseudo random number testing functions will be rewritten, but
mpz_probab_prime_p will be retained for compatibility.

The plan is to add some higher-level function that accepts some sort
of "probability" argument instead of a "reps" argument.

I also plan to add an efficient range trial division function, that
users can invoke explicitly.  There should be several entry points for
whatever miller-rabin-like functions we have, one for truly random
numbers (where trial dividing should be done) and one for numbers
where a miller-rabin-like functions should be done invoked directly.

Range trial division should be done by accumulating primes modulo n,
where n is the number we're testing.  At some clever intervals, we
compute gcd of the accumulated number and n.  Such an approach would
beat the current naive trial division code of mpz_probab_prime_p by a
large factor.

Ref: http://www.trnicely.net/misc/mpzspsp.html
Ref: http://www.trnicely.net/misc/bpsw.html

-- 
Torbjörn