Sichere Primzahl

In der Zahlentheorie ist eine sichere Primzahl (von englisch safe prime) eine Primzahl q∈ℙ der Form q=2p+1, wobei p∈ℙ ebenfalls prim sein muss. Die dazugehörige Primzahl p heißt Sophie-Germain-Primzahl.

Namensgebung

Diese Primzahlen heißen „sicher“, weil sie mit starken Primzahlen verwandt sind. Starke Primzahlen q∈ℕ sind Primzahlen, wenn (in ihrer kryptologischen Definition) sowohl q−1 als auch q+1 „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 q=2p+1 hat die Zahl q−1=2p den großen Primfaktor p, weshalb die sichere Primzahl q zumindest ein Kriterium für starke Primzahlen erfüllt.

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

Sichere Primzahlen spielen auch in der Kryptologie eine wichtige Rolle.

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-
liste a		Primzahl pDezimalstellen
von p		EntdeckungsdatumEntdeckerQuelle
1 1958. 2618163402417⋅21290001−1 388342 29. Februar 2016 Scott Brown (USA)
2 2001. 18543637900515⋅2666668−1 200701 4. oder 9. April 2012 Lee Blyth (AUS)
3 2018. 183027⋅2265441−1 79911 22. März 2010 Tom Wu
4 2027. 648621027630345⋅2253825−1 76424 18. November 2009 Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai
5 2028. 620366307356565⋅2253825−1 76424 2. November 2009 Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai
6 2048. 1068669447⋅2211088−1 63553 17. Mai 2020 Michael Kwok
7 2055. 99064503957⋅2200009−1 60220 1. April 2016 S. Urushihata
8 2072. 12443794755⋅2184516−1 55555 9. September 2021 Serge Batalov
9 2073. 21749869755⋅2184515−1 55555 9. September 2021 Serge Batalov
10 2074. 14901867165⋅2184515−1 55555 9. September 2021 Serge Batalov
a 
Stand: 18. Dezember 2021; der Rang verrät nur, an welcher Stelle diese Primzahlen in dieser Primzahlliste auftauchen

Eigenschaften

Mit anderen Worten: q≡5(mod6).
Beweis:
Alle Zahlen der Restklassen n≡0(mod6) oder n≡2(mod6) oder n≡4(mod6) sind gerade und demnach durch 2 teilbar.
Die Sophie-Germain-Primzahl p=2 führt auf die sichere Primzahl q=2⋅2+1=5 und diese erfüllt die Bedingung q≡5(mod6).
Alle Zahlen der Restklassen n≡0(mod6) oder n≡3(mod6) sind durch 3 teilbar.
Die Sophie-Germain-Primzahl p=3 führt auf die sichere Primzahl q=2⋅3+1=7 und diese erfüllt die Bedingung q≡5(mod6) nicht, ist aber aus dieser Behauptung ohnehin ausgenommen.
Zwar existieren Primzahlen in der Restklasse p≡1(mod6), jedoch würde man dadurch wegen q=2p+1=2⋅(6n+1)+1=12n+3=3⋅(4n+1) sichere „Primzahlen“ erhalten, die durch 3 teilbar wären und somit keine Primzahlen sein können.
Als einzige Sechser-Restklasse für sichere Primzahlen q bleibt somit die Restklasse q≡5(mod6) übrig. ◻
Mit anderen Worten: q≡3(mod4).
Beweis:
Bis auf die erste Sophie-Germain-Primzahl p=2 (welche auf die sichere Primzahl q=2⋅2+1=5 führt und für die diese Behauptung nicht stimmt) sind alle anderen Primzahlen ungerade, haben also die Form p=2n+1 mit n∈ℕ. Jede sichere Primzahl hat somit die Form q=2p+1=2(2n+1)+1=4n+3, was zu zeigen war. ◻
Mit anderen Worten: q≡11(mod12).
Beweis:
Alle Sophie-Germain-Primzahlen p>3 führen auf die sicheren Primzahlen q=2p+1>2⋅3+1=7 und haben die Form p=6k+5 (siehe Beweis). Somit gilt für die sichere Primzahl q=2p+1=2⋅(6k+5)+1=12k+11, was zu zeigen war. ◻
3 ist ein quadratischer Rest modulo q.
Beweis:
Sichere Primzahlen haben die Form q=2p+1 mit p∈ℙ. Wegen der Voraussetzung q>7=2p+1 ist p>3. (Ungerade) Primzahlen p>3 erfüllen aber die Kongruenz p≡1(mod6) oder p≡5(mod6), weil alle ungeraden Zahlen der Form n≡3(mod6) durch 3 teilbar sind. Primzahlen der Form p≡1(mod6) können keine Sophie-Germain-Primzahlen sein, weil dann q=2p+1≡2⋅1+1=3(mod6) durch 3 teilbar wäre und somit keine sicheren Primzahlen sind. Es bleibt nur p≡5(mod6) übrig, also ist p≡5(mod12) oder p≡5+6=11(mod12). Somit ist in beiden Fällen q=2p+1≡2⋅5+1≡2⋅11+1=23≡11(mod12). Es gibt aber den mathematischen Satz, dass 3 ein quadratischer Rest modulo q ist, genau dann, wenn q≡1(mod12) oder q≡−1≡11(mod12) ist. Somit ist 3 ein quadratischer Rest modulo q, was zu zeigen war. ◻
q teilt 3q−12−1.
Beweis:
Weil 3 ein quadratischer Rest modulo q ist, gilt folgende Kongruenz: 3q−12≡1(modq). Daraus folgt direkt, dass q ein Teiler von 3q−12−1 ist. ◻
q ist Teiler derjenigen Mersenne-Zahl, dessen Exponent die dazugehörige Sophie-Germain-Primzahl ist.
Mit anderen Worten: q teilt Mp mit p=q−12
(siehe auch Teilbarkeitseigenschaften der Mersenne-Zahlen)
Beispiel:
Es ist q=23≡7(mod8). Dann ist die dazugehörige Sophie-Germain-Primzahl p=23−12=11.
Tatsächlich ist q=23 Teiler von M11=211−1=2048−1=2047=23⋅89.
Beweis:
Fermat-Primzahlen sind von der Form F=q=2n+1. Daraus folgt, dass F−12=q−12=p=2n−1 eine Zweierpotenz, aber keine (Sophie-Germain-)Primzahl ist (außer für p=21 und somit für q=2⋅2+1=5). Somit kann die Fermat-Primzahl F keine sichere Zahl sein, was zu beweisen war. ◻
Beweis:
Weiter oben wurde bewiesen, dass alle sicheren Primzahlen mit Ausnahme von q=7 die Form q=6k2+5=6(k2+1)−1=:6k−1 haben. Mersenne-Primzahlen sind von der Form p=2m−1. Somit müsste 2m−1=6k−1 sein und deswegen wäre 2m=6k. 2m ist aber niemals durch 6 teilbar, woraus folgt, dass niemals eine Mersenne-Primzahl gleichzeitig eine sichere Primzahl sein darf (mit Ausnahme von q=7=23−1). ◻
Beweis:
Der Beweis liegt in der Definition solcher Cunningham-Ketten: a0=p (also eine Sophie-Germain-Primzahl), alle weiteren Folgenglieder haben die Form an+1=2⋅an+1 und sind somit laut Definition sichere Primzahlen. ◻
Die Zahl q beendet die Cunningham-Kette, sie ist also das letzte Folgenglied dieser Kette.
Beweis:
Das nächste Folgenglied dieser Kette wäre 2⋅(10k+7)+1=20k+15=5⋅(4k+3) und wäre somit durch 5 teilbar und deswegen keine Primzahl mehr. ◻
Ist p≡1(mod4), dann gilt:
q=2p+1 ist eine sichere Primzahl genau dann, wenn q=2p+1 Teiler von 2p+1 ist
Ist p≡3(mod4), dann gilt:
q=2p+1 ist eine sichere Primzahl genau dann, wenn q=2p+1 Teiler von 2p−1 ist

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.