Sichere Primzahl

In der Zahlentheorie ist eine sichere Primzahl (von englisch safe prime) 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.^[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.

Rang	Rang in Primzahl- liste ^a^[2]^[3]	Primzahl $p$	Dezimalstellen von $p$	Entdeckungsdatum	Entdecker	Quelle
1	1958.	$2618163402417\cdot 2^{1290001}-1$	$388342$	29. Februar 2016	Scott Brown (USA)	^[4]
2	2001.	$18543637900515\cdot 2^{666668}-1$	$200701$	4. oder 9. April 2012	Lee Blyth (AUS)	^[5]
3	2018.	$183027\cdot 2^{265441}-1$	$79911$	22. März 2010	Tom Wu	^[6]
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	^[7]
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	^[8]
6	2048.	$1068669447\cdot 2^{211088}-1$	$63553$	17. Mai 2020	Michael Kwok	^[9]
7	2055.	$99064503957\cdot 2^{200009}-1$	$60220$	1. April 2016	S. Urushihata	^[10]
8	2072.	$12443794755\cdot 2^{184516}-1$	$55555$	9. September 2021	Serge Batalov	^[11]
9	2073.	$21749869755\cdot 2^{184515}-1$	$55555$	9. September 2021	Serge Batalov	^[12]
10	2074.	$14901867165\cdot 2^{184515}-1$	$55555$	9. September 2021	Serge 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 $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{\pmod {6}}

.

Beweis:

Alle Zahlen der Restklassen

n\equiv 0{\pmod {6}}

oder

n\equiv 2{\pmod {6}}

oder

n\equiv 4{\pmod {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{\pmod {6}}

.

Alle Zahlen der Restklassen

n\equiv 0{\pmod {6}}

oder

n\equiv 3{\pmod {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{\pmod {6}}

nicht, ist aber aus dieser Behauptung ohnehin ausgenommen.

Zwar existieren Primzahlen in der Restklasse

p\equiv 1{\pmod {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{\pmod {6}}

übrig.

\Box

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{\pmod {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.

\Box

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{\pmod {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.

\Box

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{\pmod {6}}

oder

p\equiv 5{\pmod {6}}

, weil alle ungeraden Zahlen der Form

n\equiv 3{\pmod {6}}

durch

3

teilbar sind. Primzahlen der Form

p\equiv 1{\pmod {6}}

können keine Sophie-Germain-Primzahlen sein, weil dann

q=2p+1\equiv 2\cdot 1+1=3{\pmod {6}}

durch

3

teilbar wäre und somit keine sicheren Primzahlen sind. Es bleibt nur

p\equiv 5{\pmod {6}}

übrig, also ist

p\equiv 5{\pmod {12}}

oder

p\equiv 5+6=11{\pmod {12}}

. Somit ist in beiden Fällen

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

3

ein quadratischer Rest modulo

q

ist, genau dann, wenn

q\equiv 1{\pmod {12}}

oder

q\equiv -1\equiv 11{\pmod {12}}

ist.^[14] Somit ist

3

ein quadratischer Rest modulo

q

, was zu zeigen war.

\Box

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{\pmod {q}}

. Daraus folgt direkt, dass

q

ein Teiler von

3^{\frac {q-1}{2}}-1

ist.

\Box

Sei $q\equiv 7{\pmod {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{\pmod {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.

\Box

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

).

\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:

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.

\Box

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.

\Box

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

Ist

p\equiv 1{\pmod {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{\pmod {4}}

, dann gilt:

q=2p+1

ist eine sichere Primzahl genau dann, wenn

q=2p+1

Teiler von

2^{p}-1

ist

Weblinks

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

Einzelnachweise

↑ Safe Prime. In: PlanetMath. (englisch)
↑ Chris K. Caldwell: The Top Twenty: Sophie Germain (p). Prime Pages, abgerufen am 24. Juni 2018.
↑ Liste der größten bekannten Primzahlen. Abgerufen am 21. Juni 2018 (englisch).
↑ Sophie-Germain-Zahl 2618163402417·2^1290001 - 1 auf Prime Pages
↑ Sophie-Germain-Zahl 18543637900515·2⁶⁶⁶⁶⁶⁸ - 1 auf Prime Pages
↑ Sophie-Germain-Zahl 183027·2²⁶⁵⁴⁴¹ - 1 auf Prime Pages
↑ Sophie-Germain-Zahl 648621027630345·2²⁵³⁸²⁵ - 1 auf Prime Pages
↑ Sophie-Germain-Zahl 620366307356565·2²⁵³⁸²⁵ - 1 auf Prime Pages
↑ Sophie-Germain-Zahl 1068669447 · 2²¹¹⁰⁸⁸ - 1 auf Prime Pages
↑ Sophie-Germain-Zahl 99064503957·2²⁰⁰⁰⁰⁹ - 1 auf Prime Pages
↑ Sophie-Germain-Zahl 12443794755·2¹⁸⁴⁵¹⁶ - 1 auf Prime Pages
↑ Sophie-Germain-Zahl 21749869755·2¹⁸⁴⁵¹⁵ - 1 auf Prime Pages
↑ Sophie-Germain-Zahl 14901867165·2¹⁸⁴⁵¹⁵ - 1 auf Prime Pages
↑ Dušan Djukić: Quadratic Congruences. Theorem 10c. The IMO Compendium Group, 2007, S. 1–12, abgerufen am 17. März 2020.
↑ Chris K. Caldwell: Proof of a result of Euler and Lagrange on Mersenne Divisors. Prime Pages, abgerufen am 14. August 2019.
↑ Henri Lifchitz: Generalization of Euler-Lagrange theorem and new primality tests. Abgerufen am 14. August 2019.

[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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

formelbasiert	Carol ((2ⁿ − 1)² − 2) \| Doppelte Mersenne (2^{2^p − 1} − 1) \| Fakultät (n! ± 1) \| Fermat (2^2ⁿ + 1) \| Kubisch (x³ − y³)/(x − y) \| Kynea ((2ⁿ + 1)² − 2) \| Leyland (x^y + y^x) \| Mersenne (2^p − 1) \| Mills (A^3ⁿ) \| Pierpont (2^u⋅3^v + 1) \| Primorial (p_n# ± 1) \| Proth (k⋅2ⁿ + 1) \| Pythagoreisch (4n + 1) \| Quartisch (x⁴ + y⁴) \| Thabit (3⋅2ⁿ − 1) \| Wagstaff ((2^p + 1)/3) \| Williams ((b-1)⋅bⁿ − 1) \| Woodall (n⋅2ⁿ − 1)
Primzahlfolgen	Bell \| Fibonacci \| Lucas \| Motzkin \| Pell \| Perrin
eigenschaftsbasiert	Elitär \| Fortunate \| Gut \| Glücklich \| Higgs \| Hochkototient \| Isoliert \| Pillai \| Ramanujan \| Regulär \| Stark \| Stern \| Wall–Sun–Sun \| Wieferich \| Wilson
basisabhängig	Belphegor \| Champernowne \| Dihedral \| Einzigartig \| Fröhlich \| Keith \| Lange \| Minimal \| Mirp \| Permutierbar \| Primeval \| Palindrom \| Repunit-Primzahl ((10ⁿ − 1)/9) \| Schwach \| Smarandache–Wellin \| Strobogrammatisch \| Tetradisch \| Trunkierbar \| Zirkular
basierend auf Tupel	Ausbalanciert (p − n, p, p + n) \| Chen \| Cousin (p, p + 4) \| Cunningham (p, 2p ± 1, …) \| Drilling (p, p + 2 oder p + 4, p + 6) \| Konstellation \| Sexy (p, p + 6) \| Sichere (p, (p − 1)/2) \| Sophie Germain (p, 2p + 1) \| Vierling (p, p + 2, p + 6, p + 8) \| Zwilling (p, p + 2) \| Zwillings-Bi-Kette (n ± 1, 2n ± 1, …)
nach Größe	Titanisch (1.000+ Stellen) \| Gigantisch (10.000+ Stellen) \| Mega (1.000.000+ Stellen) \| Beva (1.000.000.000+ Stellen)

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Eisspeedway

Sichere Primzahl

Inhaltsverzeichnis

Namensgebung

Beispiele

Eigenschaften

Weblinks

Einzelnachweise