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

[Brett Kuntz]

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.

2. Miller-Rabin is a Fermat primality test to base N, where N is a randomly chosen number between 2, and 2 less than the number being tested. This process is repeated for X amount of rounds using a different random base each time. The provable probability of being "lied" to by the algorithm is 1/4 (25%). This means by repeating the test for enough rounds you can be really sure a number is prime.

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. IE: If you pass in 50 rounds to the function, it'll do the B-PSW, and if that passes that, it will begin doing up to 26 M-R rounds.

4. Even though the math proves 1/4 (25%) chance of being lied to by M-R, in reality using a Fermat primality test to base 2 is more than enough to know you've got a prime number, especially if the prime number is huge. For example, in all of the 40-bit numbers in existence (549,755,813,888 in total), the amount that are prime is 20,051,180,846, and the amount that are Pseudo prime to base 2 is just 5,777. So even though 40-bit numbers are tiny in comparison to the largest primes known, we still have a rare 1 in 3,470,865 chance of being lied to by a base 2 test. For REALLY large, randomly chosen odd numbers, the chance of you ever accidentally stumbling upon a Pseudo prime is 0%. It'll never happen. Do be warned though that an adversary can easily generate a large pseudo prime to base 2 quite easily to fool you. But if you yourself are just having fun with primes, and trying to find large ones, and you're sure they are truly random... then once you pass a Base 2 test you've definitely found one. You can follow it up with the Lucas test to be sure, and some M-R random base tests. But a Fermat test to base 2 is the fastest test to run.

5. If you're searching for very large primes, the fastest way will be to use a GPU to sieve potential candidates doing bulk small prime testing and have the potential candidates piped back to the CPU to run a Fermat base 2 test.

6. For really long running algorithms that are also memory intensive please keep in mind one or more SEU (https://en.wikipedia.org/wiki/Single-event_upset) can occur giving a false result one way or another.

-Brett




----- Original Message -----
From: "Dennis Clarke" <dclarke at blastwave.org>
To: gmp-discuss at gmplib.org
Sent: Wednesday, April 29, 2026 4:27:09 PM
Subject: Does the number of reps for mpz_probab_prime_p() really change much?

Dear Numerical deities : 

I was fascinated by the manpage for mpz_probab_prime_p() at 

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[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. 

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. 

Is that just the way things are ? 

Also, whatever happened to GMP-ECM? [2] 

-- 
-- 
Dennis Clarke 
RISC-V/SPARC/PPC/ARM/CISC 
UNIX and Linux spoken 

[1] https://git.sr.ht/~blastwave/bw/tree/bw/item/gmp_mpfr/pair.c 

[2] is there a definitive place/URL where the most recent GMP-ECM 
code work resides? 


-- 
-- 
Dennis Clarke 
RISC-V/SPARC/PPC/ARM/CISC 
UNIX and Linux spoken 

_______________________________________________ 
gmp-discuss mailing list 
gmp-discuss at gmplib.org 
https://gmplib.org/mailman/listinfo/gmp-discuss