Probable prime

In number theory, a PRP number (from English probable prime) is a positive integer $n\in \mathbb {N}$ that is very likely to be a prime number because a probabilistic prime number test marks it as a possible prime number. It satisfies conditions that prime numbers also satisfy, but most composite numbers do not. However, a definitive proof that this number is indeed prime cannot yet be given with such a test.

PRP numbers may eventually turn out to be composite, although probabilistic primality tests (such as Fermat's primality test) tend to suggest that they are prime numbers. If it turns out that a PRP number is indeed composite, it is called a pseudoprime.

There are also "real" tests for prime numbers (like the simple division by all prime numbers, the so-called sample division), but for numbers above a certain size these tests would take too long even for computers (at the moment the sample division tests up to about $2^{32}=4294967296$ ), so for very large numbers one rather chooses the above probabilistic prime tests. They are faster, but also "less accurate" (in the sense of prime number / no prime number). With these tests one cannot determine with absolute certainty whether the given number is a prime number or not. However, one can make the probability that the PRP number is a composite number very small by applying several different probabilistic prime number tests to the PRP number under investigation.

PRP numbers are usually very large, because otherwise you could easily test the primality. Currently, 10,000 PRP numbers are known, all of which have more than 50,000 digits.

A PRP number that "passes" (in the sense of "looks like a prime number") the Fermat prime number test with some base is called a base a PRP number. It is either actually a prime number or a Fermat pseudoprime number in base .

A PRP number that "passes" (in the sense of "looks like a prime") the somewhat stricter Solovay-Strassen test with some base is called a base a Euler PRP number. It is either actually a prime number or an Euler pseudoprime number in base .

A PRP number that "passes" (in the sense of "looks like a prime") the even stricter Miller-Rabin test with some base {\displaystyleis called a strict base a PRP number (SPRP). It is either actually a prime number or a strong pseudoprime number in base .

A PRP number in base that does not "pass" the Miller-Rabin test with a certain base (and thus is neither prime nor strong pseudoprime in base ) is called a weak PRP number in base a. It is not a prime number.

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.