PRP-Zahl

In der Zahlentheorie ist eine PRP-Zahl (vom englischen probable prime) eine positive ganze Zahl ${\displaystyle n\in \mathbb {N} }$, die sehr wahrscheinlich eine Primzahl ist, weil ein probabilistischer Primzahltest diese als mögliche Primzahl kennzeichnet. Sie erfüllt Bedingungen, die auch Primzahlen erfüllen, die meisten zusammengesetzten Zahlen aber nicht. Ein endgültiger Beweis, dass diese Zahl tatsächlich prim ist, kann mit so einem Test aber noch nicht gegeben werden.

PRP-Zahlen können s​ich letztendlich a​uch als zusammengesetzt herausstellen, wenngleich d​ie probabilistischen Primzahltests (wie z​um Beispiel d​er Fermatsche Primzahltest) e​her dafür sprechen, d​ass es s​ich um Primzahlen handelt. Stellt s​ich heraus, d​ass eine PRP-Zahl tatsächlich zusammengesetzt ist, s​o nennt m​an sie Pseudoprimzahl.

Es gibt auch „echte“ Primzahltests (wie zum Beispiel das einfache Durchdividieren durch alle Primzahlen, die sogenannte Probedivision), allerdings würden diese Tests bei Zahlen ab einer gewissen Größe auch für Computer zu lange dauern (momentan testet man bei der Probedivision bis etwa ${\displaystyle 2^{32}=4294967296}$),[1] deswegen wählt man bei sehr großen Zahlen eher obige probabilistische Primzahltests. Sie sind schneller, dafür aber auch „ungenauer“ (im Sinne von Primzahl / keine Primzahl). Mit diesen Tests kann man nicht mit absoluter Sicherheit feststellen, ob die gegebene Zahl eine Primzahl ist oder nicht. Man kann die Wahrscheinlichkeit, dass es sich bei der PRP-Zahl um eine zusammengesetzte Zahl handelt, aber sehr klein machen, indem man bei der zu untersuchenden PRP-Zahl mehrere verschiedene probabilistische Primzahltests anwendet.

PRP-Zahlen s​ind in d​er Regel s​ehr groß, w​eil man s​onst die Primalität problemlos testen könnte. Momentan k​ennt man 10.000 PRP-Zahlen, d​ie allesamt m​ehr als 50.000 Stellen haben.[1]

Eine PRP-Zahl, die beim Fermatschen Primzahltest mit einer gewissen Basis ${\displaystyle a}$ „durchkommt“ (im Sinne von „schaut aus wie eine Primzahl“) nennt man PRP-Zahl zur Basis a. Sie ist entweder tatsächlich eine Primzahl oder eine Fermatsche Pseudoprimzahl zur Basis ${\displaystyle a}$.

Eine PRP-Zahl, die beim etwas strengeren Solovay-Strassen-Test mit einer gewissen Basis ${\displaystyle a}$ „durchkommt“ (im Sinne von „schaut aus wie eine Primzahl“) nennt man Euler-PRP-Zahl zur Basis a. Sie ist entweder tatsächlich eine Primzahl oder eine Eulersche Pseudoprimzahl zur Basis ${\displaystyle a}$.

Eine PRP-Zahl, die beim noch strengeren Miller-Rabin-Test mit einer gewissen Basis ${\displaystyle a}$ „durchkommt“ (im Sinne von „schaut aus wie eine Primzahl“) nennt man strenge PRP-Zahl (SPRP) zur Basis a. Sie ist entweder tatsächlich eine Primzahl oder eine starke Pseudoprimzahl zur Basis ${\displaystyle a}$.

Eine PRP-Zahl zur Basis ${\displaystyle a}$, die beim Miller-Rabin-Test mit einer gewissen Basis ${\displaystyle a}$ nicht „durchkommt“ (und somit weder Primzahl noch starke Pseudoprimzahl zur Basis ${\displaystyle a}$ ist) nennt man schwache PRP-Zahl zur Basis a. Sie ist keine Primzahl.

Eigenschaften

• PRP-Zahlen müssen mindestens bei einem probabilistischen Primzahltest „durchkommen“ (also den Anschein erwecken, dass sie prim sein könnten).
• PRP-Zahlen sind gute Kandidaten für probabilistische Primzahltests.

Häufigkeiten

• Bis ${\displaystyle x=25\cdot 10^{9}}$ gibt es:[2]

* 1091987405 Primzahlen, davon sind 1091987404 ungerade Primzahlen (nur die Primzahl 2 ist gerade)

* 21853 Fermatsche Pseudoprimzahlen zur Basis 2

* 11347 Eulersche Pseudoprimzahlen zur Basis 2

* 4842 Starke Pseudoprimzahlen zur Basis 2

* 2163 Carmichael-Zahlen

Dies bedeutet, dass man schon mit einem einzigen probabilistischen Primzahltest, zum Beispiel dem Fermatschen Primzahltest, sehr gute Ergebnisse erzielen kann:

Unter ${\displaystyle x=25\cdot 10^{9}}$ (also unter 25 Milliarden) gibt es ${\displaystyle \pi (x)=1.091.987.405}$ Primzahlen (${\displaystyle 1.091.987.404}$ davon sind ungerade) und nur ${\displaystyle 21853}$ Fermatsche Pseudoprimzahlen zur Basis 2. Der Fermatsche Primzahltest zur Basis 2 würde, wenn man alle 25 Milliarden Zahlen testen würde, genau ${\displaystyle 1.091.987.404+21.853=1.092.009.257}$ mal eine PRP-Zahl melden. Nur bei ${\displaystyle 21853}$ PRP-Zahlen würde sich herausstellen, dass sie eine Pseudoprimzahl und somit zusammengesetzt ist. Das bedeutet, dass nur ${\displaystyle {\frac {21853}{1092009257}}\approx 0{,}002\,\%}$ der PRP-Zahlen, die man mit dem Fermatschen Primzahltest herausgefunden hat, sich als zusammengesetzt entpuppen. Macht man einen weiteren Primzahltest mit einer anderen Basis ungleich 2, so verringert sich dieser Prozentsatz noch weiter.

• Sei ${\displaystyle P(n)}$ die ${\displaystyle n}$-te Primzahl. Die kleinsten ungeraden Zahlen, bei denen der Miller-Rabin-Test mit Basis ${\displaystyle a\leq P(n)}$ eine vermeintliche Primzahl (also keine Zusammengesetztheit) meldet, sind die folgenden:

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

Beispiele:

* Die kleinste Zahl, bei der sich der Miller-Rabin-Test mit Basis ${\displaystyle a=2}$ „irrt“ (im Sinne von „Primzahl, dabei in Wirklichkeit doch zusammengesetzt“) ist ${\displaystyle 2047=23\cdot 89}$.

* Die kleinste Zahl, bei der sich der Miller-Rabin-Test sowohl mit Basis ${\displaystyle a=2}$ als auch mit Basis ${\displaystyle a=3}$ „irrt“ (im Sinne von „Primzahl, dabei in Wirklichkeit doch zusammengesetzt“) ist ${\displaystyle 1373653=829\cdot 1657}$.

* Die kleinste Zahl, bei der sich der Miller-Rabin-Test sowohl mit Basis ${\displaystyle a=2}$ als auch mit den Basen ${\displaystyle a=3,5,7,11}$ und ${\displaystyle 13}$ „irrt“ (im Sinne von „Primzahl, dabei in Wirklichkeit doch zusammengesetzt“) ist ${\displaystyle 3474749660383=1303\cdot 16927\cdot 157543}$.

Das bedeutet, dass man, wenn man wissen will, ob eine Zahl ${\displaystyle n<3.474.749.660.383}$ prim ist oder nicht, lediglich mit dem Miller-Rabin-Test mit den sechs Basen ${\displaystyle a=2,3,5,7,11}$ und ${\displaystyle 13}$ „drüberfahren“ muss, um sicher entscheiden zu können, ob es sich um eine Primzahl handelt oder nicht.

Beispiele

• Man will wissen, ob die Zahl ${\displaystyle n=2363418209}$ eine Primzahl ist oder nicht.

Schritt 1: Probedivision

Man kontrolliert, ob es eine Primzahl gibt, die ein Teiler von ${\displaystyle n}$ ist. Man dividiert ${\displaystyle n}$ durch die ersten Primzahlen, also durch ${\displaystyle 2,3,5,7,11,13,17}$ und ${\displaystyle 19}$ (oder weiter) und stellt fest, dass diese Zahlen keine Teiler von ${\displaystyle n=2363418209}$ sind. Man müsste ${\displaystyle n}$ durch alle Primzahlen ${\displaystyle p}$ teilen, für welche ${\displaystyle p\leq {\sqrt {2363418209}}\approx 48615}$ gilt. Dies erscheint aber zu aufwändig. Somit geht man weiter zu

Schritt 2: Probabilistischer Primzahltest, zum Beispiel der Fermatsche Primzahltest:

Jede Primzahl ${\displaystyle p}$ und jede dazu teilerfremde natürliche Zahl ${\displaystyle a}$ erfüllt folgende Kongruenz:

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

Bei uns ist möglicherweise ${\displaystyle n=2363418209}$ eine Primzahl, wir setzen ${\displaystyle p=2363418209}$. Wir kontrollieren, ob mit ${\displaystyle a=2}$ obige Kongruenz erfüllt ist. Man erhält

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

Ganz offensichtlich erfüllt die Zahl ${\displaystyle n=2363418209}$ nicht das Primzahlkriterium des Fermatschen Primzahltests und ist deswegen sowohl keine PRP-Zahl (zur Basis ${\displaystyle 2}$) als auch keine Primzahl. Welche Teiler diese Zahl hat, ist ein anderes, bei hohen Zahlen wesentlich schwierigeres Problem (in diesem Fall ist ${\displaystyle n=2363418209=48611\cdot 48619}$).

Nun f​olgt eine Zahl, d​eren Primzahlbestimmung e​twas schwieriger ist:

• Man will wissen, ob die Zahl ${\displaystyle n=399001}$ eine Primzahl ist oder nicht.

Schritt 1: Probedivision

Man kontrolliert, ob es eine Primzahl gibt, die ein Teiler von ${\displaystyle n}$ ist. Man dividiert ${\displaystyle n}$ durch die ersten Primzahlen, also durch ${\displaystyle 2,3,5,7,11,13,17}$ und ${\displaystyle 19}$ und stellt fest, dass diese Zahlen keine Teiler von ${\displaystyle n=399001}$ sind. Man müsste ${\displaystyle n}$ durch alle Primzahlen teilen, welche ${\displaystyle \leq {\sqrt {399001}}\approx 631,7}$ sind. Dies erscheint aber zu aufwändig. Somit geht man weiter zu

Schritt 2: Probabilistischer Primzahltest, zum Beispiel der Fermatsche Primzahltest:

Jede Primzahl ${\displaystyle p}$ und jede dazu teilerfremde natürliche Zahl ${\displaystyle a}$ erfüllt folgende Kongruenz:

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

Bei uns ist möglicherweise ${\displaystyle n=399001}$ eine Primzahl, wir setzen ${\displaystyle p=399001}$. Wir kontrollieren, ob mit ${\displaystyle a=2}$ obige Kongruenz erfüllt ist. Man erhält tatsächlich

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

Die Zahl ${\displaystyle n=399001}$ ist somit eine PRP-Zahl zur Basis ${\displaystyle 2}$ und entweder tatsächlich eine Primzahl, oder sie ist eine Fermatsche Pseudoprimzahl zur Basis ${\displaystyle 2}$.

Man wiederholt diese Kongruenz, diesmal mit ${\displaystyle a=3}$:

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

Die Zahl ${\displaystyle n=399001}$ ist somit auch eine PRP-Zahl zur Basis ${\displaystyle 3}$ und entweder tatsächlich eine Primzahl, oder es ist eine Fermatsche Pseudoprimzahl zur Basis ${\displaystyle 3}$.

Man wiederholt diesen Test mit ${\displaystyle a=5,7,11,13}$ und ${\displaystyle 17}$ und erhält als Ergebnis jedes Mal, dass ${\displaystyle n=399001}$ entweder tatsächlich eine Primzahl, oder jeweils eine Fermatsche Pseudoprimzahl zur Basis ${\displaystyle a=5,7,11,13}$ und ${\displaystyle 17}$ ist.

Es ist ${\displaystyle n=399001}$ auf jeden Fall eine PRP-Zahl, da sie mindestens einen Primzahltest „erfolgreich“ überstanden hat (im Sinne von „könnte eine Primzahl sein“). Der Fermatsche Primzahltest deutet eher auf eine Primzahl hin. Man geht weiter zu

Schritt 3: ein anderer probabilistischer Primzahltest, zum Beispiel der Solovay-Strassen-Test

Sei ${\displaystyle n=399001}$, ${\displaystyle a=2}$ und ${\displaystyle b:=a^{\frac {n-1}{2}}{\pmod {n}}}$. Dann ist

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

Es ist ${\displaystyle b=1}$, somit kann es sich bei ${\displaystyle n=399001}$ um eine Primzahl oder eine Eulersche Pseudoprimzahl handeln. Nun berechnet man das Jacobi-Symbol ${\displaystyle J(a,n)=J(2,399001)}$:

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

Der Solovay-Strassen-Test liefert also keine Aussage (wäre ${\displaystyle J(2,399001)\not \equiv b{\pmod {399001}}}$, wäre ${\displaystyle n}$ zusammengesetzt), ${\displaystyle n=399001}$ ist eine Euler-PRP-Zahl zur Basis ${\displaystyle 2}$ und kann eine Primzahl oder eine Eulersche Pseudoprimzahl zur Basis ${\displaystyle 2}$ sein.

Man wiederholt diese Tests mit ${\displaystyle a=3,5,7,11,13,17}$ und ${\displaystyle 19}$ und erhält als Ergebnis jedes Mal, dass ${\displaystyle n=399001}$ entweder tatsächlich eine Primzahl, oder jeweils eine Eulersche Pseudoprimzahl zur Basis ${\displaystyle a=3,5,7,11,13,17}$ und ${\displaystyle 19}$ ist. Man fährt fort mit

Schritt 4: ein anderer probabilistischer Primzahltest, zum Beispiel der Miller-Rabin-Test

Zuerst wählt man eine Zahl ${\displaystyle a}$ aus der Menge ${\displaystyle \{2,3,\ldots ,n-2=398999\}}$. Der nächste Schritt ist ein Test, den nur Primzahlen und starke Pseudoprimzahlen (zur Basis ${\displaystyle a}$) bestehen. Man berechnet ${\displaystyle d}$ (ungerade) und ${\displaystyle j}$, so dass

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

und prüft dann, ob entweder

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

oder

${\displaystyle a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}}$ für ein ${\displaystyle r}$ mit ${\displaystyle 0\leq r<j}$

gilt.

Wir wählen ${\displaystyle a=2}$ und erhalten

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

Somit ist ${\displaystyle d=49875}$ und ${\displaystyle j=3}$. Man kontrolliert nun obige Kongruenz

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

und stellt somit fest, dass ${\displaystyle n=399001}$ keine Primzahl ist. Es ist also gesichert, dass sie zusammengesetzt sein muss. Welche Primteiler sie hat, weiß man aber nicht. Hätte man beim Schritt 1 bis zur Zahl ${\displaystyle 31}$ weitergemacht, hätte man festgestellt, dass ${\displaystyle 399001:31=12871}$ ist und somit die Zahl ${\displaystyle 31}$ als Primteiler hat. Das Problem ist, dass man bei großen Zahlen irgendwann mit den Probedivisionen aufhören muss. Die Zahl ${\displaystyle n=399001}$ ist im Speziellen sogar eine Carmichael-Zahl und eine absolute Eulersche Pseudoprimzahl und erfüllt somit viele Eigenschaften von Primzahlen, obwohl sie keine ist. Normalerweise erkennt man schneller, ob eine PRP-Zahl eine Primzahl ist oder nicht.

Liste von Pseudoprimzahlen

Die folgenden Zahlen s​ind die kleinsten Fermatschen Pseudoprimzahlen z​ur Basis 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, … (Folge A001567 in OEIS)

Die folgenden Zahlen s​ind die kleinsten Fermatschen Pseudoprimzahlen z​ur Basis 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, … (Folge A005935 in OEIS)

Weitere Fermatsche Pseudoprimzahlen s​iehe hier.

Die folgenden Zahlen s​ind die kleinsten Eulerschen Pseudoprimzahlen z​ur Basis 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, … (Folge A006970 in OEIS)

Die folgenden Zahlen s​ind die kleinsten Eulerschen Pseudoprimzahlen z​ur Basis 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, … (Folge A262051 in OEIS)

Weitere Eulerschen Pseudoprimzahlen s​iehe hier.

Die folgenden Zahlen s​ind die kleinsten starken Pseudoprimzahlen z​ur Basis 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, … (Folge A001262 in OEIS)

Die folgenden Zahlen s​ind die kleinsten starken Pseudoprimzahlen z​ur Basis 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, … (Folge A020229 in OEIS)

Weitere starke Pseudoprimzahlen s​iehe hier.

Die folgenden Zahlen s​ind die kleinsten Carmichael-Zahlen:

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, … (Folge A002997 in OEIS)

Diese Zahlen sind für den Fermatschen Primzahltest ungeeignet, weil sie bezüglich jeder zur zu untersuchenden Zahl ${\displaystyle n}$ teilerfremden Basis ${\displaystyle a}$ eine Fermatsche Pseudoprimzahl ist.

Die folgenden Zahlen s​ind die kleinsten absoluten Eulerschen Pseudoprimzahlen:

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, … (Folge A002997 in OEIS)

Diese Zahlen sind für den Solovay-Strassen-Test ungeeignet, weil sie bezüglich jeder zur zu untersuchenden Zahl ${\displaystyle n}$ teilerfremden Basis ${\displaystyle a}$ eine Eulersche Pseudoprimzahl ist.

Die zehn größten PRP-Zahlen

Es f​olgt eine Liste d​er momentan 10 größten PRP-Zahlen, a​lso von Zahlen, d​ie wahrscheinlich Primzahlen sind, v​on denen m​an es a​ber noch n​icht sicher weiß. Der vorletzten Spalte k​ann man entnehmen, u​m welche Art v​on Primzahl e​s sich handeln würde, w​enn sich herausstellt, d​ass diese Zahl tatsächlich e​inen Primzahl ist. Der letzten Spalte k​ann man entnehmen, d​ie wievieltgrößte Primzahl d​ie jeweilige PRP-Zahl wäre, w​enn diese (und n​ur diese) s​ich tatsächlich a​ls Primzahl herausstellen würde (Stand: 4. September 2021):

Rang	PRP-Zahl[1]	Anzahl der Stellen	Entdecker	Datum der Entdeckung	Anmerkung	theoretischer Primzahlrang[3]
01.	${\displaystyle {\frac {10^{8177207}-1}{9}}}$	8177207	Ryan Propper, Sergey Batalov	8. Mai 2021	wäre die größte Repunit	011.
02.	${\displaystyle {\frac {10^{5794777}-1}{9}}}$	5794777	Ryan Propper, Sergey Batalov	20. April 2021	wäre die zweitgrößte Repunit	017.
03.	${\displaystyle {\frac {2^{15135397}+1}{3}}}$	4556209	Ryan Propper	Juni 2021	wäre die größte Wagstaff-Primzahl	027.
04.	${\displaystyle 2^{13380298}-27}$	4027872	Jeff Gilchrist, Vincent Diepeveen, Tony Reix, Paul Underwood	März 2021		035.
05.	${\displaystyle {\frac {2^{13372531}+1}{3}}}$	4025533	Ryan Propper	September 2013	wäre die zweitgrößte Wagstaff-Primzahl	035.
06.	${\displaystyle {\frac {2^{13347311}+1}{3}}}$	4017941	Ryan Propper	September 2013	wäre die drittgrößte Wagstaff-Primzahl	035.
07.	${\displaystyle {\frac {2^{12503723}-2^{6251862}+1}{5}}={\frac {(2^{6251862}-1)^{2}+1}{10}}}$	3763995	Ryan Propper, Sergey Batalov	Juli 2020	wäre der zweite Primfaktor der verallgemeinerten Mersenne-Zahl ${\displaystyle 2^{12503723}-2^{6251862}+1}$	040.
08.	${\displaystyle {\frac {2^{10443557}-1}{37289325994807}}}$	3143811	GIMPS-fre_games	Juli 2020	wäre der zweite Primfaktor der Mersenne-Zahl ${\displaystyle M_{10443557}}$	065.
09.	${\displaystyle 2^{9092392}+40291}$	2737083	Engracio Esmenda / Five or Bust	Februar 2011	wäre eine Lösung vom dualen Sierpiński-Problem für ${\displaystyle k=40291}$	078.
10.	${\displaystyle {\frac {17^{1990523}-1}{16}}}$	2449236	Paul Bourdelais	August 2020		091.

Weblinks

• Eric W. Weisstein: Probable Prime. In: MathWorld (englisch).
• Chris K. Caldwell: probable prime. Prime Pages - The Prime Glossary, abgerufen am 27. Mai 2021.

Einzelnachweise

1. Henri Lifchitz, Renaud Lifchitz: PRP Records - Probable Primes Top 10000. PRP Records, abgerufen am 27. Mai 2021.
2. Carl Pomerance, J. L. Selfridge, Samuel S. Wagstaff Jr.: The pseudoprimes to 25·10⁹. Mathematics of Computation, 35 (151), S. 1003–1026, abgerufen am 27. Mai 2021.
3. Liste der größten bekannten Primzahlen (englisch). Abgerufen am 4. September 2021.