mpz_millerrabin
Torbjorn Granlund
tg at swox.com
Mon Jan 21 13:24:17 CET 2008
[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
More information about the gmp-devel
mailing list