PRP-Zahl

• 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.

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

1.091.987.405 Primzahlen, davon sind alle bis auf eine (die 2) ungerade

0.000.021.853 Fermatsche Pseudoprimzahlen zur Basis a = 2

0.000.011.347 Eulersche Pseudoprimzahlen zur Basis a = 2

0.000.004.842 Starke Pseudoprimzahlen zur Basis a = 2

0.000.002.163 Carmichael-Zahlen

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

Bis ${\displaystyle x=25\cdot 10^{9}}$ (25 Milliarden) gibt es ${\displaystyle \pi (x)}$ = 1.091.987.405 Primzahlen und nur 21.853 Fermatsche Pseudoprimzahlen zur Basis 2. Der Fermatsche Primzahltest zur Basis 2 würde, wenn man alle 25 Milliarden Zahlen testen würde, genau 1.091.987.404 + 21.853 = 1.092.009.257 mal eine PRP-Zahl melden. Bei 21.853 PRP-Zahlen würde sich herausstellen, dass sie nur Pseudoprimzahlen und somit zusammengesetzt sind, was ${\displaystyle {\tfrac {21.853}{1.092.009.257}}\approx 0{,}002\,\%}$ der PRP-Zahlen sind. Ein weiterer Primzahltest mit einer anderen Basis als 2 verringert die Wahrscheinlichkeit weiter.

• Sei ${\displaystyle P(n)}$ die ${\displaystyle n}$-te Primzahl. Die kleinsten ungeraden Zahlen, bei denen der Miller-Rabin-Test für jede 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 a = 2 „irrt“ (im Sinne von „Primzahl, dabei in Wirklichkeit doch zusammengesetzt“), ist:

2047 = 23 · 89.

• Die kleinste Zahl, bei der sich der Miller-Rabin-Test sowohl mit Basis a = 2 als auch mit Basis a = 3 „irrt“ (im Sinne von „Primzahl, dabei in Wirklichkeit doch zusammengesetzt“) ist:

1.373.653 = 829 · 1657.

• Die kleinste Zahl, bei der sich der Miller-Rabin-Test sowohl mit Basis a = 2 als auch mit den Basen a = 3, 5, 7, 11 und 13 „irrt“ (im Sinne von „Primzahl, dabei in Wirklichkeit doch zusammengesetzt“), ist:

3.474.749.660.383 = 1.303 · 16.927 · 157.543.

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

• Man will wissen, ob die Zahl ${\displaystyle n=2.363.418.209}$ 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.^[3] 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 folgt eine Zahl, deren Primzahlbestimmung etwas 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.

Die folgenden Zahlen sind die kleinsten Fermatschen Pseudoprimzahlen zur 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 sind die kleinsten Fermatschen Pseudoprimzahlen zur 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 siehe hier.

Die folgenden Zahlen sind die kleinsten Eulerschen Pseudoprimzahlen zur 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 sind die kleinsten Eulerschen Pseudoprimzahlen zur 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 siehe hier.

Die folgenden Zahlen sind die kleinsten starken Pseudoprimzahlen zur 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 sind die kleinsten starken Pseudoprimzahlen zur 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 siehe hier.

Die folgenden Zahlen sind 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 sind 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.

Es folgt eine Liste der momentan 10 größten PRP-Zahlen, also von Zahlen, die wahrscheinlich Primzahlen sind, von denen man es aber noch nicht sicher weiß. Der vorletzten Spalte kann man entnehmen, um welche Art von Primzahl es sich handeln würde, wenn sich herausstellt, dass diese Zahl tatsächlich einen Primzahl ist. Der letzten Spalte kann man entnehmen, die wievieltgrößte Primzahl die jeweilige PRP-Zahl wäre, wenn diese (und nur diese) sich tatsächlich als Primzahl herausstellen würde (Stand: 26. Dezember 2025):

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