Sichere Primzahl

In der Zahlentheorie ist eine sichere Primzahl (von Vorlage:EnS) eine Primzahl $q\in \mathbb{P}$ der Form $q=2p+1$, wobei $p\in \mathbb{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\in \mathbb{N}$ 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, … (Vorlage:OEIS)

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

Rang	Rang in Primzahl- listeVorlage:FN	Primzahl $p$	Dezimalstellen von $p$	Entdeckungsdatum	Entdecker	Quelle
1	1958.	$2618163402417\cdot 2^{1290001}-1$	$388342$	29. Februar 2016	Scott Brown (USA)
2	2001.	$18543637900515\cdot 2^{666668}-1$	$200701$	4. oder 9. April 2012	Lee Blyth (AUS)
3	2018.	$183027\cdot 2^{265441}-1$	$79911$	22. März 2010	Tom Wu
4	2027.	$648621027630345\cdot 2^{253825}-1$	$76424$	18. November 2009	Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai
5	2028.	$620366307356565\cdot 2^{253825}-1$	$76424$	2. November 2009	Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai
6	2048.	$1068669447\cdot 2^{211088}-1$	$63553$	17. Mai 2020	Michael Kwok
7	2055.	$99064503957\cdot 2^{200009}-1$	$60220$	1. April 2016	S. Urushihata
8	2072.	$12443794755\cdot 2^{184516}-1$	$55555$	9. September 2021	Serge Batalov
9	2073.	$21749869755\cdot 2^{184515}-1$	$55555$	9. September 2021	Serge Batalov
10	2074.	$14901867165\cdot 2^{184515}-1$	$55555$	9. September 2021	Serge Batalov

Eigenschaften

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

Mit anderen Worten: $q\equiv 5(\mathrm{mod}6)$.

Beweis:

Alle Zahlen der Restklassen $n\equiv 0(\mathrm{mod}6)$ oder $n\equiv 2(\mathrm{mod}6)$ oder $n\equiv 4(\mathrm{mod}6)$ sind gerade und demnach durch $2$ teilbar.

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

Alle Zahlen der Restklassen $n\equiv 0(\mathrm{mod}6)$ oder $n\equiv 3(\mathrm{mod}6)$ sind durch $3$ teilbar.

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

Zwar existieren Primzahlen in der Restklasse $p\equiv 1(\mathrm{mod}6)$, jedoch würde man dadurch wegen $q=2p+1=2\cdot (6n+1)+1=12n+3=3\cdot (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\equiv 5(\mathrm{mod}6)$ übrig. $◻$

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

Mit anderen Worten: $q\equiv 3(\mathrm{mod}4)$.

Beweis:

Bis auf die erste Sophie-Germain-Primzahl $p=2$ (welche auf die sichere Primzahl $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 $p=2n+1$ mit $n\in \mathbb{N}$. Jede sichere Primzahl hat somit die Form $q=2p+1=2(2n+1)+1=4n+3$, was zu zeigen war. $◻$

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

Mit anderen Worten: $q\equiv 11(\mathrm{mod}12)$.

Beweis:

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

• Für alle sicheren Primzahlen $q>7$ gilt:

$3$ ist ein quadratischer Rest modulo $q$.

Beweis:

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

• Für alle sicheren Primzahlen $q>7$ gilt:

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

Beweis:

Weil $3$ ein quadratischer Rest modulo $q$ ist, gilt folgende Kongruenz: $3^{\frac{q-1}{2}}\equiv 1(\mathrm{mod}q)$. Daraus folgt direkt, dass $q$ ein Teiler von $3^{\frac{q-1}{2}}-1$ ist. $◻$

• Sei $q\equiv 7(\mathrm{mod}8)$ eine sichere Primzahl. Dann gilt:

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

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

(siehe auch Teilbarkeitseigenschaften der Mersenne-Zahlen)

Beispiel:

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

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

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

Beweis:

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

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

Beweis:

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

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

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

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\cdot (10k+7)+1=20k+15=5\cdot (4k+3)$ und wäre somit durch $5$ teilbar und deswegen keine Primzahl mehr. $◻$

• Sei $p\in \mathbb{P}$ eine Primzahl. Dann gilt:

Ist $p\equiv 1(\mathrm{mod}4)$, dann gilt:

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

Ist $p\equiv 3(\mathrm{mod}4)$, dann gilt:

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

Weblinks

• Vorlage:MathWorld
• Vorlage:PlanetMath