Does the number of reps for mpz_probab_prime_p() really change much?

[marco.bodrato at tutanota.com]

Ciao,
30 apr 2026, 07:29 da kuntz at shaw.ca:

> A brief overview of probable prime testing:
>
> 1. Baillie-PSW is an algorithm that first does a Fermat primality test to base 2, then if that passes, it does a strong Lucas test. If both of those pass, it is assumed with very high probability the number is a prime. No pseudo primes have ever been found to pass both tests, and I believe they've tested all numbers up to 2^68.
>

To my knowledge, "up to 2^64", but based on the work of a single person.

If you take the database of "base-2 Fermatpseudoprimes below below 264" from
http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html
you can test all numbers, and all of them are detected as composite by our implementation.We did this some years ago:
https://gmplib.org/list-archives/gmp-devel/2019-January/005178.html

GMP can take into account the fact that the BPSW test has no false positives up to 2^64
it's enough to compile the library defining to 1
GMP_BPSW_NOFALSEPOSITIVES_UPTO_64BITS
https://gmplib.org/repo/gmp/file/tip/mpz/millerrabin.c#l56


> 3. GMP first does a B-PSW, and if that passes, and reps is 25 or higher, it'll start doing M-R rounds (minus 24). Someone somewhere decided that passing a B-PSW test is worth at least the equivalent of> 24 M-R tests.
>

That someone was me :-) We may say that the current implementation with "reps" set to 24 has less known composite numbers passing the test as "pseudoprimes" than the previous implementation with the same number of "reps". But that's not a mathematical argument.
But the original message asked...

> ----- Original Message -----
> From: "Dennis Clarke" <dclarke at blastwave.org>
>
> After writing up something[1] to go looking for twin primes p and p+2 
> it seemed reasonable to mess with the "reps" number. No matter what 
> I set past 24 the results really do not change. Is this a feature or 
> function that only gets interesting for really really big numbers up 
> in the 10^90 zone? Just curious. 
>

The "reps" parameter changes the number of the Miller-Rabin tests.

The M-R test is not deterministic, so even a very large number of
repetitions can not change the state "definitely/probably" prime.

If you fully trust the BPSW test (and our implementation),
then larger repetitions are not needed.

> My code suggests that input 2462906046175243 has results 50% certain 
> and the rest are probably primes. Maybe. Changing the reps to 48 or 
> downwards to 15 seems to make no difference.
>

The function returns 2 (definitely prime) if our implementation
was fully tested on that range. I.e. currently for values smaller than 41*2^46https://gmplib.org/repo/gmp/rev/3273cc0d5ca9
(but that limit was just pushed in the developers repository, not jet released)It returns 1 (probably prime) for larger values not detected as composite.
Changing "reps" will not change the value from 1 to 2,
but it could change it from 1 o 0, if a composite not detected by the
initial tests is detected by the repeated Miller-Rabin tests.
In that case the library should write out a Warning:
"A counterexample to BPSW was found!"
But our library does not write warnings,
even if it detects something unusual.

Ĝis,
m

.. 
https://vado.li/dc-bodrato