Does the number of reps for mpz_probab_prime_p() really change much?
Dennis Clarke
dclarke at blastwave.org
Wed Apr 29 06:38:04 CEST 2026
I was fascinated by the manpage for mpz_probab_prime_p() :
https://gmplib.org/manual/Number-Theoretic-Functions
5.9 Number Theoretic Functions
Function: int mpz_probab_prime_p (const mpz_t n, int reps)
Determine whether n is prime. Return 2 if n is definitely prime,
return 1 if n is probably prime (without being certain),
or return 0 if n is definitely non-prime.
This function performs some trial divisions, a Baillie-PSW probable
prime test, then reps-24 Miller-Rabin probabilistic primality tests.
A higher 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 an asymptotic probability of less
than 4^(-reps). Reasonable values of reps are between 15 and 50.
GMP versions up to and including 6.1.2 did not use the Baillie-PSW
primality test. In those older versions of GMP, this function
performed reps Miller-Rabin tests.
Well that looks like just way too much fun to pass up playing with.
After writing up something 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.
My mess around code thing is here :
https://git.sr.ht/~blastwave/bw/tree/bw/item/gmp_mpfr/pair.c
Where I see at input 2462906046175243 the results are 50% certain
and the rest are probably primes. Changing the reps to 48 or down
to 15 makes no difference. At least not with that number input.
Is that just the way things are ?
--
--
Dennis Clarke
RISC-V/SPARC/PPC/ARM/CISC
UNIX and Linux spoken
More information about the gmp-devel
mailing list