Sichere Primzahl

In der Zahlentheorie ist eine sichere Primzahl (von englisch safe prime) eine Primzahl ${\displaystyle q\in \mathbb {P} }$ der Form ${\displaystyle q=2p+1}$, wobei ${\displaystyle p\in \mathbb {P} }$ ebenfalls prim sein muss. Die dazugehörige Primzahl ${\displaystyle p}$ heißt Sophie-Germain-Primzahl.

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

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

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

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.

• Mit Ausnahme der sicheren Primzahl ${\displaystyle q=7}$ haben alle sicheren Primzahlen die Form ${\displaystyle q=6k+5}$ mit einer ganzen Zahl ${\displaystyle k\in \mathbb {N} }$.

Mit anderen Worten: ${\displaystyle q\equiv 5{\pmod {6}}}$.

Beweis:

Alle Zahlen der Restklassen ${\displaystyle n\equiv 0{\pmod {6}}}$ oder ${\displaystyle n\equiv 2{\pmod {6}}}$ oder ${\displaystyle n\equiv 4{\pmod {6}}}$ sind gerade und demnach durch ${\displaystyle 2}$ teilbar.

Die Sophie-Germain-Primzahl ${\displaystyle p=2}$ führt auf die sichere Primzahl ${\displaystyle q=2\cdot 2+1=5}$ und diese erfüllt die Bedingung ${\displaystyle q\equiv 5{\pmod {6}}}$.

Alle Zahlen der Restklassen ${\displaystyle n\equiv 0{\pmod {6}}}$ oder ${\displaystyle n\equiv 3{\pmod {6}}}$ sind durch ${\displaystyle 3}$ teilbar.

Die Sophie-Germain-Primzahl ${\displaystyle p=3}$ führt auf die sichere Primzahl ${\displaystyle q=2\cdot 3+1=7}$ und diese erfüllt die Bedingung ${\displaystyle q\equiv 5{\pmod {6}}}$ nicht, ist aber aus dieser Behauptung ohnehin ausgenommen.

Zwar existieren Primzahlen in der Restklasse ${\displaystyle p\equiv 1{\pmod {6}}}$, jedoch würde man dadurch wegen ${\displaystyle q=2p+1=2\cdot (6n+1)+1=12n+3=3\cdot (4n+1)}$ sichere „Primzahlen“ erhalten, die durch ${\displaystyle 3}$ teilbar wären und somit keine Primzahlen sein können.

Als einzige Sechser-Restklasse für sichere Primzahlen ${\displaystyle q}$ bleibt somit die Restklasse ${\displaystyle q\equiv 5{\pmod {6}}}$ übrig. ${\displaystyle \Box }$

• Mit Ausnahme der sicheren Primzahl ${\displaystyle q=5}$ haben alle sicheren Primzahlen die Form ${\displaystyle q=4k+3}$ mit einer ganzen Zahl ${\displaystyle k\in \mathbb {N} }$.

Mit anderen Worten: ${\displaystyle q\equiv 3{\pmod {4}}}$.

Beweis:

Bis auf die erste Sophie-Germain-Primzahl ${\displaystyle p=2}$ (welche auf die sichere Primzahl ${\displaystyle q=2\cdot 2+1=5}$ führt und für die diese Behauptung nicht stimmt) sind alle anderen Primzahlen ungerade, haben also die Form ${\displaystyle p=2n+1}$ mit ${\displaystyle n\in \mathbb {N} }$. Jede sichere Primzahl hat somit die Form ${\displaystyle q=2p+1=2(2n+1)+1=4n+3}$, was zu zeigen war. ${\displaystyle \Box }$

• Mit Ausnahme der sicheren Primzahlen ${\displaystyle q=5}$ und ${\displaystyle q=7}$ haben alle sicheren Primzahlen die Form ${\displaystyle q=12k+11}$ mit einer ganzen Zahl ${\displaystyle k\in \mathbb {N} }$.

Mit anderen Worten: ${\displaystyle q\equiv 11{\pmod {12}}}$.

Beweis:

Alle Sophie-Germain-Primzahlen ${\displaystyle p>3}$ führen auf die sicheren Primzahlen ${\displaystyle q=2p+1>2\cdot 3+1=7}$ und haben die Form ${\displaystyle p=6k+5}$ (siehe Beweis). Somit gilt für die sichere Primzahl ${\displaystyle q=2p+1=2\cdot (6k+5)+1=12k+11}$, was zu zeigen war. ${\displaystyle \Box }$

• Für alle sicheren Primzahlen ${\displaystyle q>7}$ gilt:

${\displaystyle 3}$ ist ein quadratischer Rest modulo ${\displaystyle q}$.

Beweis:

Sichere Primzahlen haben die Form ${\displaystyle q=2p+1}$ mit ${\displaystyle p\in \mathbb {P} }$. Wegen der Voraussetzung ${\displaystyle q>7=2p+1}$ ist ${\displaystyle p>3}$. (Ungerade) Primzahlen ${\displaystyle p>3}$ erfüllen aber die Kongruenz ${\displaystyle p\equiv 1{\pmod {6}}}$ oder ${\displaystyle p\equiv 5{\pmod {6}}}$, weil alle ungeraden Zahlen der Form ${\displaystyle n\equiv 3{\pmod {6}}}$ durch ${\displaystyle 3}$ teilbar sind. Primzahlen der Form ${\displaystyle p\equiv 1{\pmod {6}}}$ können keine Sophie-Germain-Primzahlen sein, weil dann ${\displaystyle q=2p+1\equiv 2\cdot 1+1=3{\pmod {6}}}$ durch ${\displaystyle 3}$ teilbar wäre und somit keine sicheren Primzahlen sind. Es bleibt nur ${\displaystyle p\equiv 5{\pmod {6}}}$ übrig, also ist ${\displaystyle p\equiv 5{\pmod {12}}}$ oder ${\displaystyle p\equiv 5+6=11{\pmod {12}}}$. Somit ist in beiden Fällen ${\displaystyle q=2p+1\equiv 2\cdot 5+1\equiv 2\cdot 11+1=23\equiv 11{\pmod {12}}}$. Es gibt aber den mathematischen Satz, dass ${\displaystyle 3}$ ein quadratischer Rest modulo ${\displaystyle q}$ ist, genau dann, wenn ${\displaystyle q\equiv 1{\pmod {12}}}$ oder ${\displaystyle q\equiv -1\equiv 11{\pmod {12}}}$ ist.^[14] Somit ist ${\displaystyle 3}$ ein quadratischer Rest modulo ${\displaystyle q}$, was zu zeigen war. ${\displaystyle \Box }$

• Für alle sicheren Primzahlen ${\displaystyle q>7}$ gilt:

${\displaystyle q}$ teilt ${\displaystyle 3^{\frac {q-1}{2}}-1}$.

Beweis:

Weil ${\displaystyle 3}$ ein quadratischer Rest modulo ${\displaystyle q}$ ist, gilt folgende Kongruenz: ${\displaystyle 3^{\frac {q-1}{2}}\equiv 1{\pmod {q}}}$. Daraus folgt direkt, dass ${\displaystyle q}$ ein Teiler von ${\displaystyle 3^{\frac {q-1}{2}}-1}$ ist. ${\displaystyle \Box }$

• Sei ${\displaystyle q\equiv 7{\pmod {8}}}$ eine sichere Primzahl. Dann gilt:

${\displaystyle q}$ ist Teiler derjenigen Mersenne-Zahl, dessen Exponent die dazugehörige Sophie-Germain-Primzahl ist.

Mit anderen Worten: ${\displaystyle q}$ teilt ${\displaystyle M_{p}}$ mit ${\displaystyle p={\frac {q-1}{2}}}$

(siehe auch Teilbarkeitseigenschaften der Mersenne-Zahlen)

Beispiel:

Es ist ${\displaystyle q=23\equiv 7{\pmod {8}}}$. Dann ist die dazugehörige Sophie-Germain-Primzahl ${\displaystyle p={\frac {23-1}{2}}=11}$.

Tatsächlich ist ${\displaystyle q=23}$ Teiler von ${\displaystyle M_{11}=2^{11}-1=2048-1=2047=23\cdot 89}$.

• Es gibt mit Ausnahme der Primzahl ${\displaystyle q=5}$ keine Fermat-Primzahlen, welche gleichzeitig sichere Primzahlen sind.

Beweis:

Fermat-Primzahlen sind von der Form ${\displaystyle F=q=2^{n}+1}$. Daraus folgt, dass ${\displaystyle {\frac {F-1}{2}}={\frac {q-1}{2}}=p=2^{n-1}}$ eine Zweierpotenz, aber keine (Sophie-Germain-)Primzahl ist (außer für ${\displaystyle p=2^{1}}$ und somit für ${\displaystyle q=2\cdot 2+1=5}$). Somit kann die Fermat-Primzahl ${\displaystyle F}$ keine sichere Zahl sein, was zu beweisen war. ${\displaystyle \Box }$

• Es gibt mit Ausnahme der Primzahl ${\displaystyle q=7}$ keine Mersenne-Primzahlen, welche gleichzeitig sichere Primzahlen sind.

Beweis:

Weiter oben wurde bewiesen, dass alle sicheren Primzahlen mit Ausnahme von ${\displaystyle q=7}$ die Form ${\displaystyle q=6k_{2}+5=6(k_{2}+1)-1=:6k-1}$ haben. Mersenne-Primzahlen sind von der Form ${\displaystyle p=2^{m}-1}$. Somit müsste ${\displaystyle 2^{m}-1=6k-1}$ sein und deswegen wäre ${\displaystyle 2^{m}=6k}$. ${\displaystyle 2^{m}}$ ist aber niemals durch ${\displaystyle 6}$ teilbar, woraus folgt, dass niemals eine Mersenne-Primzahl gleichzeitig eine sichere Primzahl sein darf (mit Ausnahme von ${\displaystyle q=7=2^{3}-1}$). ${\displaystyle \Box }$

• 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: ${\displaystyle a_{0}=p}$ (also eine Sophie-Germain-Primzahl), alle weiteren Folgenglieder haben die Form ${\displaystyle a_{n+1}=2\cdot a_{n}+1}$ und sind somit laut Definition sichere Primzahlen. ${\displaystyle \Box }$

• Sei ${\displaystyle q}$ eine sichere Primzahl der Form ${\displaystyle q=10k+7}$ (sie soll also mit ${\displaystyle 7}$ enden), welche in einer Cunningham-Kette vorkommt. Dann gilt:

Die Zahl ${\displaystyle q}$ beendet die Cunningham-Kette, sie ist also das letzte Folgenglied dieser Kette.

Beweis:

Das nächste Folgenglied dieser Kette wäre ${\displaystyle 2\cdot (10k+7)+1=20k+15=5\cdot (4k+3)}$ und wäre somit durch ${\displaystyle 5}$ teilbar und deswegen keine Primzahl mehr. ${\displaystyle \Box }$

• Sei ${\displaystyle p\in \mathbb {P} }$ eine Primzahl. Dann gilt:^[15][16]

Ist ${\displaystyle p\equiv 1{\pmod {4}}}$, dann gilt:

${\displaystyle q=2p+1}$ ist eine sichere Primzahl genau dann, wenn ${\displaystyle q=2p+1}$ Teiler von ${\displaystyle 2^{p}+1}$ ist

Ist ${\displaystyle p\equiv 3{\pmod {4}}}$, dann gilt:

${\displaystyle q=2p+1}$ ist eine sichere Primzahl genau dann, wenn ${\displaystyle q=2p+1}$ Teiler von ${\displaystyle 2^{p}-1}$ ist

• Eric W. Weisstein: Sophie Germain Prime. In: MathWorld (englisch).
• Safe Prime. In: PlanetMath. (englisch)

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·2^1290001 - 1 auf Prime Pages
5. ↑ Sophie-Germain-Zahl 18543637900515·2⁶⁶⁶⁶⁶⁸ - 1 auf Prime Pages
6. ↑ Sophie-Germain-Zahl 183027·2²⁶⁵⁴⁴¹ - 1 auf Prime Pages
7. ↑ Sophie-Germain-Zahl 648621027630345·2²⁵³⁸²⁵ - 1 auf Prime Pages
8. ↑ Sophie-Germain-Zahl 620366307356565·2²⁵³⁸²⁵ - 1 auf Prime Pages
9. ↑ Sophie-Germain-Zahl 1068669447 · 2²¹¹⁰⁸⁸ - 1 auf Prime Pages
10. ↑ Sophie-Germain-Zahl 99064503957·2²⁰⁰⁰⁰⁹ - 1 auf Prime Pages
11. ↑ Sophie-Germain-Zahl 12443794755·2¹⁸⁴⁵¹⁶ - 1 auf Prime Pages
12. ↑ Sophie-Germain-Zahl 21749869755·2¹⁸⁴⁵¹⁵ - 1 auf Prime Pages
13. ↑ Sophie-Germain-Zahl 14901867165·2¹⁸⁴⁵¹⁵ - 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.