Sichere Primzahl

In der Zahlentheorie ist eine sichere Primzahl (von englisch safe prime) eine Primzahl der Form , wobei ebenfalls prim sein muss. Die dazugehörige Primzahl heißt Sophie-Germain-Primzahl.

Namensgebung

Diese Primzahlen heißen „sicher“, weil sie mit starken Primzahlen verwandt sind. Starke Primzahlen sind Primzahlen, wenn (in ihrer kryptologischen Definition) sowohl als auch „große“ Primfaktoren (im Sinne von „viel größer kann ein Primfaktor nicht werden als knapp halb so groß wie die Zahl selber“) besitzen. Für sichere Primzahlen hat die Zahl den großen Primfaktor , weshalb die sichere Primzahl zumindest ein Kriterium für starke Primzahlen erfüllt.

Die Dauer von Methoden, die Zahlen faktorisieren, welche als Primfaktor haben, hängt zum Teil von der Größe des Primfaktors von ab, wie zum Beispiel bei der Pollard-p-1-Methode.

Sichere Primzahlen spielen auch in der Kryptologie eine wichtige Rolle.[1]

Beispiele

Die kleinsten sicheren Primzahlen sind die folgenden:

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2039, 2063, 2099, 2207, 2447, 2459, 2579, 2819, 2879, 2903, … (Folge A005385 in OEIS)

Der folgenden Liste kann man die 10 größten bekannten sicheren Primzahlen entnehmen. Sämtliche Entdecker dieser Primzahlen sind Teilnehmer des PrimeGrid-Projektes.

RangRang in
Primzahl-
listea[2][3]
Primzahl Dezimalstellen
von
EntdeckungsdatumEntdeckerQuelle
11958.29. Februar 2016Scott Brown (USA)[4]
22001.4. oder 9. April 2012Lee Blyth (AUS)[5]
32018.22. März 2010Tom Wu[6]
42027.18. November 2009Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai[7]
52028.2. November 2009Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai[8]
62048.17. Mai 2020Michael Kwok[9]
72055.1. April 2016S. Urushihata[10]
82072.9. September 2021Serge Batalov[11]
92073.9. September 2021Serge Batalov[12]
102074.9. September 2021Serge Batalov[13]
a Stand: 18. Dezember 2021; der Rang verrät nur, an welcher Stelle diese Primzahlen in dieser Primzahlliste auftauchen

Eigenschaften

  • Mit Ausnahme der sicheren Primzahl haben alle sicheren Primzahlen die Form mit einer ganzen Zahl .
Mit anderen Worten: .
Beweis:
Alle Zahlen der Restklassen oder oder sind gerade und demnach durch teilbar.
Die Sophie-Germain-Primzahl führt auf die sichere Primzahl und diese erfüllt die Bedingung .
Alle Zahlen der Restklassen oder sind durch teilbar.
Die Sophie-Germain-Primzahl führt auf die sichere Primzahl und diese erfüllt die Bedingung nicht, ist aber aus dieser Behauptung ohnehin ausgenommen.
Zwar existieren Primzahlen in der Restklasse , jedoch würde man dadurch wegen sichere „Primzahlen“ erhalten, die durch teilbar wären und somit keine Primzahlen sein können.
Als einzige Sechser-Restklasse für sichere Primzahlen bleibt somit die Restklasse übrig.
  • Mit Ausnahme der sicheren Primzahl haben alle sicheren Primzahlen die Form mit einer ganzen Zahl .
Mit anderen Worten: .
Beweis:
Bis auf die erste Sophie-Germain-Primzahl (welche auf die sichere Primzahl führt und für die diese Behauptung nicht stimmt) sind alle anderen Primzahlen ungerade, haben also die Form mit . Jede sichere Primzahl hat somit die Form , was zu zeigen war.
  • Mit Ausnahme der sicheren Primzahlen und haben alle sicheren Primzahlen die Form mit einer ganzen Zahl .
Mit anderen Worten: .
Beweis:
Alle Sophie-Germain-Primzahlen führen auf die sicheren Primzahlen und haben die Form (siehe Beweis). Somit gilt für die sichere Primzahl , was zu zeigen war.
  • Für alle sicheren Primzahlen gilt:
ist ein quadratischer Rest modulo .
Beweis:
Sichere Primzahlen haben die Form mit . Wegen der Voraussetzung ist . (Ungerade) Primzahlen erfüllen aber die Kongruenz oder , weil alle ungeraden Zahlen der Form durch teilbar sind. Primzahlen der Form können keine Sophie-Germain-Primzahlen sein, weil dann durch teilbar wäre und somit keine sicheren Primzahlen sind. Es bleibt nur übrig, also ist oder . Somit ist in beiden Fällen . Es gibt aber den mathematischen Satz, dass ein quadratischer Rest modulo ist, genau dann, wenn oder ist.[14] Somit ist ein quadratischer Rest modulo , was zu zeigen war.
  • Für alle sicheren Primzahlen gilt:
teilt .
Beweis:
Weil ein quadratischer Rest modulo ist, gilt folgende Kongruenz: . Daraus folgt direkt, dass ein Teiler von ist.
  • Sei eine sichere Primzahl. Dann gilt:
ist Teiler derjenigen Mersenne-Zahl, dessen Exponent die dazugehörige Sophie-Germain-Primzahl ist.
Mit anderen Worten: teilt mit
(siehe auch Teilbarkeitseigenschaften der Mersenne-Zahlen)
Beispiel:
Es ist . Dann ist die dazugehörige Sophie-Germain-Primzahl .
Tatsächlich ist Teiler von .
  • Es gibt mit Ausnahme der Primzahl keine Fermat-Primzahlen, welche gleichzeitig sichere Primzahlen sind.
Beweis:
Fermat-Primzahlen sind von der Form . Daraus folgt, dass eine Zweierpotenz, aber keine (Sophie-Germain-)Primzahl ist (außer für und somit für ). Somit kann die Fermat-Primzahl keine sichere Zahl sein, was zu beweisen war.
  • Es gibt mit Ausnahme der Primzahl keine Mersenne-Primzahlen, welche gleichzeitig sichere Primzahlen sind.
Beweis:
Weiter oben wurde bewiesen, dass alle sicheren Primzahlen mit Ausnahme von die Form haben. Mersenne-Primzahlen sind von der Form . Somit müsste sein und deswegen wäre . ist aber niemals durch teilbar, woraus folgt, dass niemals eine Mersenne-Primzahl gleichzeitig eine sichere Primzahl sein darf (mit Ausnahme von ).
  • Jedes Folgenglied einer Cunningham-Kette der ersten Art mit Ausnahme des ersten Gliedes einer solchen Kette ist eine sichere Primzahl.
Beweis:
Der Beweis liegt in der Definition solcher Cunningham-Ketten: (also eine Sophie-Germain-Primzahl), alle weiteren Folgenglieder haben die Form und sind somit laut Definition sichere Primzahlen.
  • Sei eine sichere Primzahl der Form (sie soll also mit enden), welche in einer Cunningham-Kette vorkommt. Dann gilt:
Die Zahl beendet die Cunningham-Kette, sie ist also das letzte Folgenglied dieser Kette.
Beweis:
Das nächste Folgenglied dieser Kette wäre und wäre somit durch teilbar und deswegen keine Primzahl mehr.
  • Sei eine Primzahl. Dann gilt:[15][16]
Ist , dann gilt:
ist eine sichere Primzahl genau dann, wenn Teiler von ist
Ist , dann gilt:
ist eine sichere Primzahl genau dann, wenn Teiler von ist

Weblinks

Einzelnachweise

  1. Safe Prime. In: PlanetMath. (englisch)
  2. Chris K. Caldwell: The Top Twenty: Sophie Germain (p). Prime Pages, abgerufen am 24. Juni 2018.
  3. Liste der größten bekannten Primzahlen. Abgerufen am 21. Juni 2018 (englisch).
  4. Sophie-Germain-Zahl 2618163402417·21290001 - 1 auf Prime Pages
  5. Sophie-Germain-Zahl 18543637900515·2666668 - 1 auf Prime Pages
  6. Sophie-Germain-Zahl 183027·2265441 - 1 auf Prime Pages
  7. Sophie-Germain-Zahl 648621027630345·2253825 - 1 auf Prime Pages
  8. Sophie-Germain-Zahl 620366307356565·2253825 - 1 auf Prime Pages
  9. Sophie-Germain-Zahl 1068669447 · 2211088 - 1 auf Prime Pages
  10. Sophie-Germain-Zahl 99064503957·2200009 - 1 auf Prime Pages
  11. Sophie-Germain-Zahl 12443794755·2184516 - 1 auf Prime Pages
  12. Sophie-Germain-Zahl 21749869755·2184515 - 1 auf Prime Pages
  13. Sophie-Germain-Zahl 14901867165·2184515 - 1 auf Prime Pages
  14. Dušan Djukić: Quadratic Congruences. Theorem 10c. The IMO Compendium Group, 2007, S. 1–12, abgerufen am 17. März 2020.
  15. Chris K. Caldwell: Proof of a result of Euler and Lagrange on Mersenne Divisors. Prime Pages, abgerufen am 14. August 2019.
  16. Henri Lifchitz: Generalization of Euler-Lagrange theorem and new primality tests. Abgerufen am 14. August 2019.