AlegsaOnline.com

Probable prime

A probable prime is an integer that passes a probabilistic primality test and is therefore likely prime; such tests are fast, widely used in cryptography, and have low but nonzero error rates.

Author: Leandro Alegsa Creation date: November 13, 2022 Last updated: June 25, 2026

Probable prime is a term from number theory for an integer that has passed one or more probabilistic primality tests and so is likely to be prime. These tests work by checking congruence relations or algebraic properties that all primes satisfy. When an integer passes a test it becomes a "probable prime" for that test: most such numbers are actually prime, but some composites (called pseudoprimes) can pass. For background see number theory sources.

Common tests and classifications

Several different tests give rise to different kinds of probable primes. Typical examples include:

Fermat probable primes: numbers n that satisfy a^(n-1) ≡ 1 (mod n) for a chosen base a (by Fermat's little theorem). See Fermat test.
Euler and Euler–Jacobi probable primes: refinements using quadratic residues to reduce false positives.
Strong probable primes (often from the Miller–Rabin test): a stricter check with much smaller error probability per random base.
Lucas probable primes and variations: tests based on recurrence sequences and algebraic properties.

Reliability and error

Probabilistic tests are designed so that a composite number will fail with high probability for a random choice of parameters. For the most commonly used strong probable prime (Miller–Rabin) test, a composite odd integer will be a strong probable prime for at most a fraction of the possible bases; this gives a concrete bound on the error per test. By repeating the test with several independent bases, the chance of mistakenly accepting a composite can be reduced to negligible levels for practical purposes.

History and development

Probable-prime tests evolved from simple consequences of Fermat's little theorem into more sophisticated algorithms that exploit group and field structure. They were refined in the 20th century and remain the fastest methods for certifying primality in large numbers in most applications. Deterministic polynomial-time algorithms for primality also exist, but they are usually slower in practical use than repeated probabilistic tests.

Uses and examples

In cryptography, probable-prime tests are routinely used to generate large primes for keys: a random odd candidate is tested until it passes several bases and is accepted as prime with high confidence. Some well-known composites illustrate limitations: 341 (11×31) is a Fermat pseudoprime to base 2, and Carmichael numbers are composites that pass Fermat tests to every base coprime to them. Practitioners therefore prefer stronger tests such as Miller–Rabin and may follow up with deterministic or certificate-producing methods like Miller–Rabin variants or provable algorithms.

Distinctions and notable facts

"Probable prime" is not a proof of primality. For rigorous guarantees one uses primality certificates or deterministic algorithms. Nevertheless, the balance of speed and extremely low error probability makes probable-prime testing the practical standard for large-number primality in computing and cryptography.

Properties

PRP numbers must at least "pass" a probabilistic primality test (i.e., appear to be prim).
PRP numbers are good candidates for probabilistic prime number tests.

Frequencies

Up to $x=25\cdot 10^{9}$ there is:

* 1091987405 prime numbers, of which 1091987404 are odd prime numbers (only the prime number 2 is even)

* 21853 Fermat pseudoprimes to base 2

* 11347 Eulerian pseudoprimes in base 2

* 4842 Strong pseudoprimes in base 2

* 2163 Carmichael numbers

This means that one can obtain very good results with just a single probabilistic prime test, for example, the Fermat prime test:

Under $x=25\cdot 10^{9}$ (that is, below 25 billion), there are π $\pi (x)=1.091.987.405$ Primes ( $1.091.987.404$ of which are odd) and only $21853$ Fermat's pseudoprimes in base 2. The Fermat's prime number test in base 2, if tested on all 25 billion numbers, would report exactly $1.091.987.404+21.853=1.092.009.257$ Report a PRP number for the first time. Only $21853$ PRP numbers would turn out to be a pseudoprime number and thus composite. This means that only ${\frac {21853}{1092009257}}\approx 0{,}002\,\%$ of the PRP numbers found using Fermat's prime test turn out to be composite. If one makes another prime number test with another base not equal to 2, this percentage decreases even more.

Let be the th prime number. The smallest odd numbers for which the Miller-Rabin test with base $a\leq P(n)$ reports a putative prime (i.e., no composition) are the following:

2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051, 3825123056546413051, 3825123056546413051, 318665857834031151167461, 3317044064679887385961981 (sequence A014233 in OEIS).

Examples:

* The smallest number for which the Miller-Rabin test with base a=2 "errs" (in the sense of "prime, yet in reality composite") is $2047=23\cdot 89$ .

* The smallest number for which the Miller-Rabin test is a=3 "wrong" (sense of "prime, yet in reality composite") both with base and a=2 with base is $1373653=829\cdot 1657$ .

* The smallest number for which the Miller-Rabin test is "wrong" both with base a=2 and with bases $a=3,5,7,11$ and "errs" (in the sense of "prime, yet in reality composite") is $3474749660383=1303\cdot 16927\cdot 157543$ .

This means that if you want to know whether a number $n<3.474.749.660.383$ is prime or not, you only have to "run over" it with the Miller-Rabin test with the six bases $a=2,3,5,7,11$ and able to decide for sure whether it is a prime number or not.

Examples

One wants to know whether the number $n=2363418209$ is a prime number or not.

Step 1: Trial division

One checks whether there is a prime number which is a divisor of One divides by the first prime numbers, i.e. by $2,3,5,7,11,13,17$ and (or further) and finds that these numbers are not divisors of $n=2363418209$ One would have to divide by all primes for which $p\leq {\sqrt {2363418209}}\approx 48615$ . However, this seems to be too complex. Thus one goes on to

Step 2: Probabilistic prime number test, for example, the Fermat prime number test:

Every prime number and every natural number partial to it satisfies the following congruence:

$a^{p-1}\equiv 1{\pmod {p}}$

With us possibly $n=2363418209$ a prime number, we set $p=2363418209$ . We check that with a=2 above congruence is satisfied. We get

$2^{2363418209-1}=2^{2363418208}\equiv 817442832\not \equiv 1{\pmod {2363418209}}$

Obviously, the number $n=2363418209$ not satisfy the prime number criterion of Fermat's prime number test and is therefore both not a PRP number (base ) and not a prime number. What divisors this number has is a different problem, much more difficult for large numbers (in this case, $n=2363418209=48611\cdot 48619$ ).

Now follows a number whose prime number determination is somewhat more difficult:

One wants to know whether the number $n=399001$ is a prime number or not.

Step 1: Trial division

One checks whether there is a prime number which is a divisor of One divides by the first prime numbers, that is, by $2,3,5,7,11,13,17$ and and finds that these numbers are not divisors of $n=399001$ One would have to divide by all prime numbers which $\leq {\sqrt {399001}}\approx 631,7$ are ≤ However, this appears to be too costly. Thus one goes on to

Step 2: Probabilistic prime number test, for example, the Fermat prime number test:

Every prime number and every natural number partial to it satisfies the following congruence:

$a^{p-1}\equiv 1{\pmod {p}}$

With us possibly $n=399001$ a prime number, we set $p=399001$ . We check that with a=2 above congruence is satisfied. We get indeed

$2^{399001-1}=2^{399000}\equiv 1{\pmod {399001}}$

Thus, the number $n=399001$ is a PRP number in base and is either actually a prime number, or it is a Fermat pseudoprime number in base .

One repeats this congruence, this time with a=3 :

$3^{399001-1}=3^{399000}\equiv 1{\pmod {399001}}$

Thus, the number $n=399001$ is also a PRP number in base and is either actually a prime number, or it is a Fermat pseudoprime number in base .

Repeat this test with $a=5,7,11,13$ and and get as a result each time that is $n=399001$ either actually a prime, or in each case a Fermat pseudoprime to the base $a=5,7,11,13$ and

It is $n=399001$ a PRP number in any case, since it has "successfully" survived at least one prime number test (in the sense of "could be a prime number"). The Fermat's prime number test is more indicative of a prime number. One goes on to

Step 3: another probabilistic prime number test, for example the Solovay-Strassen test.

Let $n=399001$ , a=2 and $b:=a^{\frac {n-1}{2}}{\pmod {n}}$ . Then

$b=2^{\frac {399001-1}{2}}\equiv 1{\pmod {399001}}$

It is b=1 , so $n=399001$ may be a prime or an Eulerian pseudoprime. Now calculate the Jacobi symbol $J(a,n)=J(2,399001)$ :

$J(2,399001)=1\equiv 1\equiv b{\pmod {399001}}$

Thus, the Solovay-Strassen test yields no statement (if $J(2,399001)\not \equiv b{\pmod {399001}}$ , would be composite), $n=399001$ is a base Euler PRP number and may be a prime or a base Euler pseudoprime }.

One repeats these tests with $a=3,5,7,11,13,17$ and and gets as result each time, that is $n=399001$ either actually a prime, or in each case an Eulerian pseudoprime to the base $a=3,5,7,11,13,17$ and One continues with

Step 4: another probabilistic prime number test, for example the Miller-Rabin test.

First, one chooses a number from the set $\{2,3,\ldots ,n-2=398999\}$ . The next step is a test that only primes and strong pseudoprimes (in base ) pass. One computes (odd) and such that

$n - 1 = d \cdot 2^j$ ,

and then checks whether either

$a^d \equiv 1 \pmod n$

$a^{d \cdot 2^r} \equiv -1 \pmod n$ for an with $0 \le r < j$

applies.

We choose a=2 and get

$n-1=399001-1=399000=49875\cdot 2^{3}=d\cdot 2^{j}$

Thus $d=49875$ and $j=3$ . We now check the above congruence

$2^{d}=2^{49875}\equiv 47896\not \equiv 1{\pmod {399001}}$

and thus establishes that $n=399001$ is not a prime number. It is therefore certain that it must be composite. Which prime divisors it has, however, is not known. If one had continued at step 1 until the number , one would have found that $399001:31=12871$ and thus has the number as a prime divisor. The problem is that with large numbers, at some point you have to stop doing trial divisions. In particular, the number $n=399001$ is even a Carmichael number and an absolute Eulerian pseudoprime, and thus satisfies many properties of primes even though it is not. Normally one recognizes faster whether a PRP number is a prime number or not.

List of pseudoprimes

The following numbers are the smallest Fermat pseudoprimes to base 2:

341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341, … (sequence A001567 in OEIS)

The following numbers are the smallest Fermat pseudoprimes to base 3:

91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, 10585, 11011, 12403, 14383, 15203, 15457, 15841, 16471, 16531, 18721, 19345, 23521, 24046, 24661, 24727, 28009, 29161, … (sequence A005935 in OEIS)

For more Fermat pseudoprimes, see here.

The following numbers are the smallest Eulerian pseudoprimes to base 2:

341, 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 5461, 6601, 8321, 8481, 10261, 10585, 12801, 15709, 15841, 16705, 18705, 25761, 29341, 30121, 31621, 33153, 34945, 41041, 42799, ... (sequence A006970 in OEIS).

The following numbers are the smallest Eulerian pseudoprimes to base 3:

121, 703, 1541, 1729, 1891, 2465, 2821, 3281, 4961, 7381, 8401, 8911, 10585, 12403, 15457, 15841, 16531, 18721, 19345, 23521, 24661, 28009, 29341, 30857, 31621, 31697, 41041, 44287, 46657, 47197, 49141, 50881, 52633, 55969, 63139, 63973, 72041, 74593, 75361, … (sequence A262051 in OEIS)

For more Eulerian pseudoprimes, see here.

The following numbers are the smallest strong pseudoprimes to base 2:

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, 104653, 130561, 196093, 220729, 233017, 252601, 253241, 256999, 271951, 280601, 314821, 357761, 390937, 458989, 476971, 486737, … (sequence A001262 in OEIS)

The following numbers are the smallest strong pseudoprimes to base 3:

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, 105163, 111361, 112141, 148417, 152551, 182527, 188191, 211411, 218791, 221761, 226801, … (sequence A020229 in OEIS)

For more strong pseudoprimes, see here.

The following numbers are the smallest Carmichael numbers:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, … (sequence A002997 in OEIS)

These numbers are unsuitable for the Fermat prime test because they are Fermat pseudoprimes with respect to any base is divisor-unrelated to the number examined.

The following numbers are the smallest absolute Eulerian pseudoprimes:

1729, 2465, 15841, 41041, 46657, 75361, 162401, 172081, 399001, 449065, 488881, 530881, 656601, 670033, 838201, 997633, 1050985, 1615681, 1773289, 1857241, 2113921, 2433601, 2455921, 2704801, 3057601, 3224065, 3581761, 3664585, 3828001, 4463641, 4903921, … (sequence A002997 in OEIS)

These numbers are unsuitable for the Solovay-Strassen test because they are Eulerian pseudoprimes with respect to any base is divisor-unrelated to the number } under investigation.

The ten biggest PRP numbers

The following is a list of the currently 10 largest PRP numbers, i.e. numbers that are probably prime numbers, but of which we do not yet know for sure. The penultimate column shows what kind of prime number it would be if it turns out that this number is indeed a prime number. The last column shows the fourth largest prime number the respective PRP number would be if this (and only this) would actually turn out to be a prime number (as of May 27, 2021):

Rank	PRP number	Number of digits	Discoverer	Date ofDiscovery	Note	TheoreticalPrimaryNumberRank
01.	${\frac {10^{8177207}-1}{9}}$	8177207	Ryan Propper, Sergey Batalov	May 8, 2021	would be the largest repunit	011.
02.	${\frac {10^{5794777}-1}{9}}$	5794777	Ryan Propper, Sergey Batalov	April 20, 2021	would be the second largest repunit	017.
03.	$2^{13380298}-27$	4027872	Jeff Gilchrist, Vincent Diepeveen, Tony Reix, Paul Underwood	March 2021		033.
04.	${\frac {2^{13372531}+1}{3}}$	4025533	Ryan Propper	September 2013	would be the largest Wagstaff prime	033.
05.	${\frac {2^{13347311}+1}{3}}$	4017941	Ryan Propper	September 2013	would be the second largest Wagstaff prime number	033.
06.	${\frac {2^{12503723}-2^{6251862}+1}{5}}={\frac {(2^{6251862}-1)^{2}+1}{10}}$	3763995	Ryan Propper, Sergey Batalov	July 2020	the second prime factor of the generalized Mersenne number would be $2^{12503723}-2^{6251862}+1$	038.
07.	${\frac {2^{10443557}-1}{37289325994807}}$	3143811	GIMPS-fre_games	July 2020	would be the second prime factor of the Mersenne number $M_{10443557}$	062.
08.	$2^{9092392}+40291$	2737083	Engracio Esmenda / Five or Bust	February 2011	would be a solution of the dual Sierpiński problem for $k=40291$	075.
09.	${\frac {17^{1990523}-1}{16}}$	2449236	Paul Bourdelais	August 2020		088.
10.	${\frac {2^{7313983}-1}{305492080276193}}$	2201714	Oliver Kruse	March 2018	would be the second prime factor of the Mersenne number $M_{7313983}$	109.