PRP number

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

PRP numbers can ultimately also turn out to be composite, although the probabilistic primality tests (such as the Fermatian primality test ) tend to suggest that they are prime numbers. If it turns out that a PRP number is actually composed, it is called a pseudoprime number .

There are also "real" primality tests (such as simply dividing through all prime numbers, the so-called trial division ), but these tests would take too long for numbers above a certain size, even for computers (at the moment the trial division tests up to about ), therefore, for very large numbers, the above probabilistic prime number tests are chosen. They are faster, but also “less precise” (in the sense of a prime / not a prime number). These tests cannot be used to determine with absolute certainty whether the given number is prime or not. However, the probability that the PRP number is a composite number can be made very small by applying several different probabilistic primality tests to the PRP number to be examined. ${\displaystyle 2^{32}=4294967296}$

PRP numbers are usually very large because otherwise the primality could be tested without any problems. We currently know 10,000 PRP numbers, all of which have more than 50,000 digits.

A PRP number that "gets through" with a certain base in Fermat's primality test (in the sense of "looks like a prime number") is called a PRP number with base a . It is either actually a prime or a Fermatian pseudoprime for the base . ${\displaystyle a}$ ${\displaystyle a}$

A PRP number that "gets through" with a certain basis in the somewhat more stringent Solovay-Strassen test (in the sense of "looks like a prime number") is called a Euler PRP number with base a . It is either actually a prime number or an Euler's pseudoprime number for the base . ${\displaystyle a}$ ${\displaystyle a}$

A PRP number that "gets through" with a certain base (in the sense of "looks like a prime number") in the even stricter Miller-Rabin test is called a strict PRP number (SPRP) with base a . It is either actually a prime or a strong pseudo- prime to the base . ${\displaystyle a}$ ${\displaystyle a}$

A PRP number for the base that does not "get through" with a certain base in the Miller-Rabin test (and is therefore neither a prime number nor a strong pseudoprime number for the base ) is called a weak PRP number for the base a . It is not a prime number. ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle a}$

properties

• PRP numbers must at least “pass” a probabilistic primality test (ie give the impression that they could be prime).
• PRP numbers are good candidates for probabilistic primality tests.

Frequencies

• Until there is: ${\displaystyle x=25\cdot 10^{9}}$

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

* 21853 Fermatsche pseudoprimes for base 2

* 11347 Euler's pseudo- prime numbers on base 2

* 4842 Strong pseudoprimes for base 2

* 2163 Carmichael numbers

This means that you can achieve very good results with a single probabilistic prime number test, for example Fermat's prime number test :

Below (i.e. below 25 billion) there are prime numbers (of which are odd) and only Fermatsche pseudoprimes for base 2. The Fermatsche prime number test for base 2 would, if one were to test all 25 billion numbers, report exactly one PRP number. Only in the case of PRP numbers would it turn out to be a pseudoprime number and thus a composite. This means that only the PRP numbers that have been found with the Fermat's primality test turn out to be composite. If you do another prime number test with a different base other than 2, this percentage is reduced even further. ${\displaystyle x=25\cdot 10^{9}}$ ${\displaystyle \pi (x)=1.091.987.405}$ ${\displaystyle 1.091.987.404}$ ${\displaystyle 21853}$ ${\displaystyle 1.091.987.404+21.853=1.092.009.257}$ ${\displaystyle 21853}$ ${\displaystyle {\frac {21853}{1092009257}}\approx 0{,}002\,\%}$

• Let the -th prime number. The smallest odd numbers for which the Miller-Rabin test with a base reports a supposed prime number (i.e. no composite) are the following: ${\displaystyle P(n)}$ ${\displaystyle n}$ ${\displaystyle a\leq P(n)}$

2047 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341,550,071,728,321, 341,550,071,728,321, 3825123056546413051, 3825123056546413051, 3825123056546413051, 318665857834031151167461, 3317044064679887385961981 (sequence A014233 in OEIS )

Examples:

* The smallest number for which the Miller-Rabin test with the base is “wrong” (in the sense of “prime number, but actually composed”) . ${\displaystyle a=2}$ ${\displaystyle 2047=23\cdot 89}$

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

* The smallest number for which the Miller-Rabin test is “wrong” with both the base and the bases and (in the sense of “prime number, but actually composed”) . ${\displaystyle a=2}$ ${\displaystyle a=3,5,7,11}$ ${\displaystyle 13}$ ${\displaystyle 3474749660383=1303\cdot 16927\cdot 157543}$

This means that if you want to know whether a number is prime or not only with the Miller-Rabin test with the six bases and to decide with certainty "hover" must, if it is a prime number or not. ${\displaystyle n<3.474.749.660.383}$ ${\displaystyle a=2,3,5,7,11}$ ${\displaystyle 13}$

Examples

• You want to know whether the number is prime or not. ${\displaystyle n=2363418209}$

Step 1: Trial Division

You check whether there is a prime number that is a divisor of . You divide by the first prime numbers, i.e. by and (or further) and find that these numbers are not divisors of . One would have to divide by all prime numbers for which applies. But this seems too time-consuming. So you go on to ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2,3,5,7,11,13,17}$ ${\displaystyle 19}$ ${\displaystyle n=2363418209}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle p\leq {\sqrt {2363418209}}\approx 48615}$

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

Every prime number and every coprime natural number fulfills the following congruence : ${\displaystyle p}$ ${\displaystyle a}$

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

We may be prime, we bet . We check whether the above congruence is fulfilled. You get ${\displaystyle n=2363418209}$ ${\displaystyle p=2363418209}$ ${\displaystyle a=2}$

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

Obviously, the number does not meet the prime number criterion of Fermat's primality test and is therefore neither a PRP number (for the base ) nor a prime number. Which factor this number has is another problem that is much more difficult with high numbers (in this case it is ). ${\displaystyle n=2363418209}$ ${\displaystyle 2}$ ${\displaystyle n=2363418209=48611\cdot 48619}$

Now follows a number whose prime number is a little more difficult:

• You want to know whether the number is prime or not. ${\displaystyle n=399001}$

Step 1: Trial Division

You check whether there is a prime number that is a divisor of . You divide by the first prime numbers, i.e. by and, and you find that these numbers are not divisors of . One would have to divide by all the prime numbers which are. But this seems too time-consuming. So you go on to ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2,3,5,7,11,13,17}$ ${\displaystyle 19}$ ${\displaystyle n=399001}$ ${\displaystyle n}$ ${\displaystyle \leq {\sqrt {399001}}\approx 631,7}$

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

Every prime number and every coprime natural number fulfills the following congruence : ${\displaystyle p}$ ${\displaystyle a}$

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

We may be prime, we bet . We check whether the above congruence is fulfilled. You actually get ${\displaystyle n=399001}$ ${\displaystyle p=399001}$ ${\displaystyle a=2}$

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

The number is thus a PRP number for the base and either actually a prime number, or it is a Fermat's pseudoprime number for the base . ${\displaystyle n=399001}$ ${\displaystyle 2}$ ${\displaystyle 2}$

This congruence is repeated, this time with : ${\displaystyle a=3}$

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

The number is thus also a PRP number for the base and either actually a prime number, or it is a Fermatian pseudoprime number for the base . ${\displaystyle n=399001}$ ${\displaystyle 3}$ ${\displaystyle 3}$

This test is repeated with and and each time the result is that either is actually a prime number or a Fermatian pseudo-prime number for the base and . ${\displaystyle a=5,7,11,13}$ ${\displaystyle 17}$ ${\displaystyle n=399001}$ ${\displaystyle a=5,7,11,13}$ ${\displaystyle 17}$

It is definitely a PRP number because it has passed at least one prime number test (in the sense of “could be a prime number”). The Fermatsche prime number test rather indicates a prime number. One goes on to ${\displaystyle n=399001}$

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

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

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

It is , so it can be a prime number or an Euler's pseudo- prime number . Now one calculates the Jacobi symbol : ${\displaystyle b=1}$ ${\displaystyle n=399001}$ ${\displaystyle J(a,n)=J(2,399001)}$

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

The Solovay-Strassen test does not provide any information (would be , would be composite), it is an Euler PRP number for the base and can be a prime number or an Euler's pseudoprime number for the base . ${\displaystyle J(2,399001)\not \equiv b{\pmod {399001}}}$ ${\displaystyle n}$ ${\displaystyle n=399001}$ ${\displaystyle 2}$ ${\displaystyle 2}$

These tests are repeated with and and each time the result is that either actually a prime number or an Euler's pseudo-prime number for the base and is. One continues with ${\displaystyle a=3,5,7,11,13,17}$ ${\displaystyle 19}$ ${\displaystyle n=399001}$ ${\displaystyle a=3,5,7,11,13,17}$ ${\displaystyle 19}$

Step 4: Another probabilistic primality test, for example the Miller-Rabin test

First you choose a number from the set . The next step is a test that only primes and strong pseudoprimes (for the base ) pass. One computes (odd) and , so that ${\displaystyle a}$ ${\displaystyle \{2,3,\ldots ,n-2=398999\}}$ ${\displaystyle a}$ ${\displaystyle d}$ ${\displaystyle j}$

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

and then checks to see if either

${\displaystyle a^{d}\equiv 1{\pmod {n}}}$

or

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

applies.

We choose and receive ${\displaystyle a=2}$

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

So is and . You now check the above congruence ${\displaystyle d=49875}$ ${\displaystyle j=3}$

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

and thus determines that is not a prime number. So it is certain that it must be put together. But one does not know which prime divisor it has. If you had continued with step 1 to the number , you would have found that is and thus has the number as a prime divisor. The problem is that with large numbers you have to stop the trial divisions at some point. In particular, the number is even a Carmichael number and an absolute Euler's pseudoprime number and thus fulfills many properties of prime numbers, although it is not. It is usually easier to tell whether a PRP number is prime or not. ${\displaystyle n=399001}$ ${\displaystyle 31}$ ${\displaystyle 399001:31=12871}$ ${\displaystyle 31}$ ${\displaystyle n=399001}$

List of pseudoprimes

The following numbers are the smallest Fermatian 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 Fermatian 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 Fermatsche pseudoprimes see here .

The following numbers are the smallest base 2 Euler's pseudoprimes:

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 base 3 Euler's pseudoprimes:

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, ... ( continuation A262051 in OEIS )

For more Euler's pseudoprimes see here .

The following numbers are the smallest strong base 2 pseudoprimes:

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 base 3 pseudoprimes:

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 figures are for the Fermat primality unsuitable because they each for under examination number regarding prime base is a Fermat pseudo prime. ${\displaystyle n}$ ${\displaystyle a}$

The following numbers are the smallest absolute Euler pseudoprimes :

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

These numbers are unsuitable for the Solovay-Strassen test because they are Euler's pseudo-prime numbers with respect to every base that is relatively prime to the number to be examined . ${\displaystyle n}$ ${\displaystyle a}$

The ten largest PRP numbers

The following is a list of the 10 largest PRP numbers at the moment, numbers that are probably prime numbers, but are not yet known for sure. The penultimate column shows what kind of prime number it would be if it turned out that this number is actually a prime number. The last column shows how much the largest prime number would be the respective PRP number if this (and only this) actually turned out to be a prime number (as of August 18, 2020):

rank	PRP number	Number of digits	Explorer	Date of discovery	annotation	theoretical prime rank
01.	${\displaystyle {\frac {2^{13372531}+1}{3}}}$	4025533	Ryan Propper	September 2013	would be the largest Wagstaff prime	028.
02.	${\displaystyle {\frac {2^{13347311}+1}{3}}}$	4017941	Ryan Propper	September 2013	would be the second largest Wagstaff prime number	028.
03.	${\displaystyle {\frac {2^{12503723}-2^{6251862}+1}{5}}={\frac {(2^{6251862}-1)^{2}+1}{10}}}$	3763995	Ryan Propper + Sergey Batalov	July 2020	would be the second prime factor of the generalized Mersenne number ${\displaystyle 2^{12503723}-2^{6251862}+1}$	031.
04th	${\displaystyle {\frac {2^{10443557}-1}{37289325994807}}}$	3143811	GIMPS -fre_games	July 2020	would be the second prime factor of the Mersenne number ${\displaystyle M_{10443557}}$	049.
05.	${\displaystyle 2^{9092392}+40291}$	2737083	Engracio Esmenda / Five or Bust	February 2011	would be a solution to the dual Sierpiński problem for ${\displaystyle k=40291}$	060.
06th	${\displaystyle {\frac {17^{1990523}-1}{16}}}$	2449236	Paul Bourdelais	August 2020		066.
07th	${\displaystyle {\frac {2^{7313983}-1}{305492080276193}}}$	2201714	Oliver Kruse	March 2018	would be the second prime factor of the Mersenne number ${\displaystyle M_{7313983}}$	073.
08th.	${\displaystyle {\frac {2^{7080247}-1}{156822217506727\cdot 11283326312536321\cdot 9632940548330339593}}}$	2131318	Gord Palameta	October 2017	would be the fourth prime factor of the Mersenne number ${\displaystyle M_{7080247}}$	079.
09.	${\displaystyle {\frac {13^{1503503}-1}{12}}}$	1674817	Paul Bourdelais	April 2020		150.
10.	${\displaystyle {\frac {10^{1600787}+1}{11}}}$	1600786	Paul Bourdelais	May 2020		163.

Individual evidence

1. ↑ ^{a b c} Henri Lifchitz, Renaud Lifchitz: PRP Records - Probable Primes Top 10000. PRP Records, accessed on August 13, 2020 . 
2. ^ Carl Pomerance, JL Selfridge, Samuel S. Wagstaff Jr .: The pseudoprimes to 25 · 10 ⁹ . Mathematics of Computation , 35 (151), pp. 1003-1026 , accessed August 13, 2020 . 
3. ↑ List of the largest known prime numbers (English). Retrieved August 13, 2020 . 

Web links

• Eric W. Weisstein : Probable Prime . In: MathWorld (English).
• Chris K. Caldwell: probable prime. Prime Pages - The Prime Glossary, accessed August 13, 2020 .