Documentation patch for mpz_millerrabin

Niels Möller nisse at
Sat Apr 13 08:55:35 UTC 2019

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 in the
> documentation.
> I wrote up what I think is a reasonable explanation of the change <http:///>
> in case that's useful.

Thanks. Some comments below.

> I'd like to help out with GMP, let me know what the best way I can
> contribute is.

If you'd like to improve the documentations, there are some white spots
in the Algorithms section, e.g., Jacobi symbol computation.
Wraparound-arithmetic may also be worth mentioning (mpn_mulmod_bnm1 and

For coding projects, see Probably not entirely
up-to-date, so ask about current status on the list if you find some of
those projects interesting.

> +This function performs some trial divisions, a Baillie-PSW probable prime
> +test, then @var{reps-24} Miller-Rabin probabilistic primality tests.  A
> +higher @var{reps} value will reduce the chances of a non-prime being
> +identified as ``probably prime''.  A composite number will be identified as a
> +prime with a probability of less than @m{4^{-reps},4^(- at var{reps})}.
> +Reasonable values of @var{reps} are between 15 and 50.

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. 

"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

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
(Internal server error).


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

More information about the gmp-devel mailing list