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 {\displaystyle 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 a"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.

A PRP number that a"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.

A PRP number that a"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.

A PRP number in base athat does anot "pass" the Miller-Rabin test with a certain base (and thus is neither prime nor strong pseudoprime in base a) 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 {\displaystyle 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 {\displaystyle x=25\cdot 10^{9}}(that is, below 25 billion), there are π {\displaystyle \pi (x)=1.091.987.405}Primes ( {\displaystyle 1.091.987.404}of which are odd) and only {\displaystyle 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 {\displaystyle 1.091.987.404+21.853=1.092.009.257}Report a PRP number for the first time. Only {\displaystyle 21853}PRP numbers would turn out to be a pseudoprime number and thus composite. This means that only {\displaystyle {\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 P(n)the nth prime number. The smallest odd numbers for which the Miller-Rabin test with base {\displaystyle 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 {\displaystyle 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=2with base is {\displaystyle 1373653=829\cdot 1657}.

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

This means that if you want to know whether a number {\displaystyle 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 {\displaystyle a=2,3,5,7,11}and 13able to decide for sure whether it is a prime number or not.

Examples

  • One wants to know whether the number {\displaystyle 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 nOne divides nby the first prime numbers, i.e. by {\displaystyle 2,3,5,7,11,13,17}and 19(or further) and finds that these numbers are not divisors of {\displaystyle n=2363418209}One would have to pdivide nby all primes for which {\displaystyle 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 pand every natural number partial to it asatisfies the following congruence:

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

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

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

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

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

  • One wants to know whether the number {\displaystyle 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 nOne divides nby the first prime numbers, that is, by {\displaystyle 2,3,5,7,11,13,17}and 19and finds that these numbers are not divisors of {\displaystyle n=399001}One would have to divide nby all prime numbers which {\displaystyle \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 pand every natural number partial to it asatisfies the following congruence:

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

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

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

Thus, the number {\displaystyle n=399001}is a PRP number in base 2and is either actually a prime number, or it is a Fermat pseudoprime number in base 2.

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

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

Thus, the number {\displaystyle n=399001}is also a PRP number in base 3and is either actually a prime number, or it is a Fermat pseudoprime number in base 3.

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

It is {\displaystyle 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 {\displaystyle n=399001}, a=2and {\displaystyle b:=a^{\frac {n-1}{2}}{\pmod {n}}}. Then

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

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

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

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

One repeats these tests with {\displaystyle a=3,5,7,11,13,17}and 19and gets as result each time, that 19is {\displaystyle n=399001}either actually a prime, or in each case an Eulerian pseudoprime to the base {\displaystyle 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 afrom the set {\displaystyle \{2,3,\ldots ,n-2=398999\}}. The next step is a test that only primes and strong pseudoprimes (in base a) pass. One computes d(odd) and jsuch that

n - 1 = d \cdot 2^j,

and then checks whether either

a^d \equiv 1 \pmod n

or

a^{d \cdot 2^r} \equiv -1 \pmod nfor an rwith 0 \le r < j

applies.

We choose a=2and get

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

Thus {\displaystyle d=49875}and {\displaystyle j=3}. We now check the above congruence

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

and thus establishes that {\displaystyle 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 31continued at step 1 until the number , one would have found that {\displaystyle 399001:31=12871}and thus has the number 31as a prime divisor. The problem is that with large numbers, at some point you have to stop doing trial divisions. In particular, the number {\displaystyle 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 ndivisor-unrelated to the number aexamined.

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 ndivisor-unrelated to the number }a 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.

{\displaystyle {\frac {10^{8177207}-1}{9}}}

8177207

Ryan Propper, Sergey Batalov

May 8, 2021

would be the largest repunit

011.

02.

{\displaystyle {\frac {10^{5794777}-1}{9}}}

5794777

Ryan Propper, Sergey Batalov

April 20, 2021

would be the second largest repunit

017.

03.

{\displaystyle 2^{13380298}-27}

4027872

Jeff Gilchrist, Vincent Diepeveen, Tony Reix, Paul Underwood

March 2021

033.

04.

{\displaystyle {\frac {2^{13372531}+1}{3}}}

4025533

Ryan Propper

September 2013

would be the largest Wagstaff prime

033.

05.

{\displaystyle {\frac {2^{13347311}+1}{3}}}

4017941

Ryan Propper

September 2013

would be the second largest Wagstaff prime number

033.

06.

{\displaystyle {\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 {\displaystyle 2^{12503723}-2^{6251862}+1}

038.

07.

{\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}}

062.

08.

{\displaystyle 2^{9092392}+40291}

2737083

Engracio Esmenda / Five or Bust

February 2011

would be a solution of the dual Sierpiński problem for {\displaystyle k=40291}

075.

09.

{\displaystyle {\frac {17^{1990523}-1}{16}}}

2449236

Paul Bourdelais

August 2020

088.

10.

{\displaystyle {\frac {2^{7313983}-1}{305492080276193}}}

2201714

Oliver Kruse

March 2018

would be the second prime factor of the Mersenne number {\displaystyle M_{7313983}}

109.


AlegsaOnline.com - 2020 / 2023 - License CC3