PRP-Zahl

Zahl, die wahrscheinlich eine Primzahl ist

In der Zahlentheorie ist eine PRP-Zahl (vom englischen probable prime) eine positive ganze Zahl , 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 sich letztendlich auch als zusammengesetzt herausstellen, wenngleich die probabilistischen Primzahltests (wie zum Beispiel der Fermatsche Primzahltest) eher dafür sprechen, dass es sich um Primzahlen handelt. Stellt sich heraus, dass eine PRP-Zahl tatsächlich zusammengesetzt ist, so nennt man 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 ),[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 sind in der Regel sehr groß, weil man sonst die Primalität problemlos testen könnte. Momentan kennt man 10.000 PRP-Zahlen, die allesamt mehr als 50.000 Stellen haben.[1]

Eine PRP-Zahl, die beim Fermatschen Primzahltest mit einer gewissen Basis „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 .

Eine PRP-Zahl, die beim etwas strengeren Solovay-Strassen-Test mit einer gewissen Basis „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 .

Eine PRP-Zahl, die beim noch strengeren Miller-Rabin-Test mit einer gewissen Basis „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 .

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

Eigenschaften

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

Bearbeiten
  • Bis   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   (also unter 25 Milliarden) gibt es   Primzahlen (  davon sind ungerade) und nur   Fermatsche Pseudoprimzahlen zur Basis 2. Der Fermatsche Primzahltest zur Basis 2 würde, wenn man alle 25 Milliarden Zahlen testen würde, genau   mal eine PRP-Zahl melden. Nur bei   PRP-Zahlen würde sich herausstellen, dass sie eine Pseudoprimzahl und somit zusammengesetzt ist. Das bedeutet, dass nur   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   die  -te Primzahl. Die kleinsten ungeraden Zahlen, bei denen der Miller-Rabin-Test für jede Basis   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   „irrt“ (im Sinne von „Primzahl, dabei in Wirklichkeit doch zusammengesetzt“) ist  .
* Die kleinste Zahl, bei der sich der Miller-Rabin-Test sowohl mit Basis   als auch mit Basis   „irrt“ (im Sinne von „Primzahl, dabei in Wirklichkeit doch zusammengesetzt“) ist  .
* Die kleinste Zahl, bei der sich der Miller-Rabin-Test sowohl mit Basis   als auch mit den Basen   und   „irrt“ (im Sinne von „Primzahl, dabei in Wirklichkeit doch zusammengesetzt“) ist  .
Das bedeutet, dass man, wenn man wissen will, ob eine Zahl   prim ist oder nicht, lediglich mit dem Miller-Rabin-Test mit den sechs Basen   und   „drüberfahren“ muss, um sicher entscheiden zu können, ob es sich um eine Primzahl handelt oder nicht.

Beispiele

Bearbeiten
  • Man will wissen, ob die Zahl   eine Primzahl ist oder nicht.
Schritt 1: Probedivision
Man kontrolliert, ob es eine Primzahl gibt, die ein Teiler von   ist. Man dividiert   durch die ersten Primzahlen, also durch   und   (oder weiter) und stellt fest, dass diese Zahlen keine Teiler von   sind. Man müsste   durch alle Primzahlen   teilen, für welche   gilt. Dies erscheint aber zu aufwändig. Somit geht man weiter zu
Schritt 2: Probabilistischer Primzahltest, zum Beispiel der Fermatsche Primzahltest:
Jede Primzahl   und jede dazu teilerfremde natürliche Zahl   erfüllt folgende Kongruenz:
 
Bei uns ist möglicherweise   eine Primzahl, wir setzen  . Wir kontrollieren, ob mit   obige Kongruenz erfüllt ist. Man erhält
 
Ganz offensichtlich erfüllt die Zahl   nicht das Primzahlkriterium des Fermatschen Primzahltests und ist deswegen sowohl keine PRP-Zahl (zur Basis  ) als auch keine Primzahl. Welche Teiler diese Zahl hat, ist ein anderes, bei hohen Zahlen wesentlich schwierigeres Problem (in diesem Fall ist  ).

Nun folgt eine Zahl, deren Primzahlbestimmung etwas schwieriger ist:

  • Man will wissen, ob die Zahl   eine Primzahl ist oder nicht.
Schritt 1: Probedivision
Man kontrolliert, ob es eine Primzahl gibt, die ein Teiler von   ist. Man dividiert   durch die ersten Primzahlen, also durch   und   und stellt fest, dass diese Zahlen keine Teiler von   sind. Man müsste   durch alle Primzahlen teilen, welche   sind. Dies erscheint aber zu aufwändig. Somit geht man weiter zu
Schritt 2: Probabilistischer Primzahltest, zum Beispiel der Fermatsche Primzahltest:
Jede Primzahl   und jede dazu teilerfremde natürliche Zahl   erfüllt folgende Kongruenz:
 
Bei uns ist möglicherweise   eine Primzahl, wir setzen  . Wir kontrollieren, ob mit   obige Kongruenz erfüllt ist. Man erhält tatsächlich
 
Die Zahl   ist somit eine PRP-Zahl zur Basis   und entweder tatsächlich eine Primzahl, oder sie ist eine Fermatsche Pseudoprimzahl zur Basis  .
Man wiederholt diese Kongruenz, diesmal mit  :
 
Die Zahl   ist somit auch eine PRP-Zahl zur Basis   und entweder tatsächlich eine Primzahl, oder es ist eine Fermatsche Pseudoprimzahl zur Basis  .
Man wiederholt diesen Test mit   und   und erhält als Ergebnis jedes Mal, dass   entweder tatsächlich eine Primzahl, oder jeweils eine Fermatsche Pseudoprimzahl zur Basis   und   ist.
Es ist   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  ,   und  . Dann ist
 
Es ist  , somit kann es sich bei   um eine Primzahl oder eine Eulersche Pseudoprimzahl handeln. Nun berechnet man das Jacobi-Symbol  :
 
Der Solovay-Strassen-Test liefert also keine Aussage (wäre  , wäre   zusammengesetzt),   ist eine Euler-PRP-Zahl zur Basis   und kann eine Primzahl oder eine Eulersche Pseudoprimzahl zur Basis   sein.
Man wiederholt diese Tests mit   und   und erhält als Ergebnis jedes Mal, dass   entweder tatsächlich eine Primzahl, oder jeweils eine Eulersche Pseudoprimzahl zur Basis   und   ist. Man fährt fort mit
Schritt 4: ein anderer probabilistischer Primzahltest, zum Beispiel der Miller-Rabin-Test
Zuerst wählt man eine Zahl   aus der Menge  . Der nächste Schritt ist ein Test, den nur Primzahlen und starke Pseudoprimzahlen (zur Basis  ) bestehen. Man berechnet   (ungerade) und  , so dass
 ,
und prüft dann, ob entweder
 
oder
  für ein   mit  
gilt.
Wir wählen   und erhalten
 
Somit ist   und  . Man kontrolliert nun obige Kongruenz
 
und stellt somit fest, dass   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   weitergemacht, hätte man festgestellt, dass   ist und somit die Zahl   als Primteiler hat. Das Problem ist, dass man bei großen Zahlen irgendwann mit den Probedivisionen aufhören muss. Die Zahl   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

Bearbeiten

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   teilerfremden Basis   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   teilerfremden Basis   eine Eulersche Pseudoprimzahl ist.

Die zehn größten PRP-Zahlen

Bearbeiten

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: 12. August 2023):

Rang PRP-Zahl[1] Anzahl
der Stellen
Entdecker Datum der
Entdeckung
Anmerkung theoretischer
Primzahlrang[3]
01.   8177207 Ryan Propper, Sergey Batalov 8. Mai 2021 wäre die größte Repunit 012.
02.   5794777 Ryan Propper, Sergey Batalov 20. April 2021 wäre die zweitgrößte Repunit 025.
03.   4556209 Ryan Propper Juni 2021 wäre die größte Wagstaff-Primzahl 045.
04.   4027872 Jeff Gilchrist, Vincent Diepeveen, Tony Reix, Paul Underwood März 2021 060.
05.   4025533 Ryan Propper September 2013 wäre die zweitgrößte Wagstaff-Primzahl 060.
06.   4017941 Ryan Propper September 2013 wäre die drittgrößte Wagstaff-Primzahl 060.
07.   3829294 Anonymous Juli 2020 wäre der vierte Primfaktor der Mersenne-Zahl   066.
08.   3789365 Eden Avidan, Naegi Makoto Mai 2023 wäre der zweite Primfaktor der Mersenne-Zahl   066.
09.   3763995 Ryan Propper, Sergey Batalov Juli 2020 wäre der zweite Primfaktor der verallgemeinerten Mersenne-Zahl   066.
10.   3143811 GIMPS-fre_games Juli 2020 wäre der zweite Primfaktor der Mersenne-Zahl   109.
Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b c 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·109. Mathematics of Computation, 35 (151), S. 1003–1026, abgerufen am 27. Mai 2021.
  3. Liste der größten bekannten Primzahlen (englisch). Abgerufen am 27. März 2022.