Documentation patch for mpz_millerrabin

Marco Bodrato bodrato at
Sat Apr 13 09:30:20 UTC 2019


Il Sab, 13 Aprile 2019 10:55 am, Niels Möller ha scritto:
> Seth Troisi <braintwo at> writes:

>> I see there are some recent changes to mpz_millerrabin around adding
>> BPSW primality test. I don't think these changes are reflected yet

>> I wrote up what I think is a reasonable explanation of the change

Yes, minimal, but useful.

>> +This function performs some trial divisions, a Baillie-PSW probable
>> prime
>> +test, then @var{reps-24} Miller-Rabin probabilistic primality tests.  A

> To make this somewhat bizarre definition make any sense, one probably
> have to mention that in earlier versions, it used to do reps
> Miller-Rabin tests.

I agree :-)

> "Reasonable values" for @var{reps} also needs some thought. I think
> passing 24 is reasonable in most cases, one will then rely on BPSW for
> recent GMP versions, and still use 24 Miller-Rabin iterations with older
> versions.

Also passing 15 is reasonable, if it was for older versions, it will be
equivalent to 24 for the jet-to-release version. I'd not touch that

> Hmm, and now I'm a bit confused, has the new BPSW code been committed
> yet? In my copy, I see it is used in mini-gmp, but not in
> mpz/pprime_p.c. And appears down at the moment

Yes it was committed, but the code was inserted in the millerrabin.c file.

changeset:   17704:d417bcef18e6
date:        Mon Nov 12 23:04:51 2018 +0100
summary:     mpz/millerrabin.c: Implement BPSW test for primality.

It was also widely tested.


More information about the gmp-devel mailing list