Quelltext der Seite Sichere Primzahl

In der [[Zahlentheorie]] ist eine '''sichere Primzahl''' (von {{enS|safe prime}}) eine [[Primzahl]] <math>q \in \mathbb P</math> der Form <math>q = 2p+1</math>, wobei <math>p \in \mathbb P</math> ebenfalls prim sein muss. Die dazugehörige Primzahl <math>p</math> heißt '''[[Sophie-Germain-Primzahl]]'''.

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

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

Sichere Primzahlen spielen auch in der [[Kryptologie]] eine wichtige Rolle.<ref>{{PlanetMath |id=SafePrime |title=Safe Prime}}</ref>

== 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, … ({{OEIS|A005385}})
Der folgenden Liste kann man die 10 größten bekannten sicheren Primzahlen entnehmen. Sämtliche Entdecker dieser Primzahlen sind Teilnehmer des [[PrimeGrid]]-Projektes.
{| class="wikitable"
|- class="hintergrundfarbe6"
! Rang || Rang in<br /> Primzahl-<br /> liste{{FN|a}}<ref>{{Internetquelle |autor=Chris K. Caldwell |url=http://primes.utm.edu/top20/page.php?id=2 |titel=The Top Twenty: Sophie Germain (p) |hrsg=Prime Pages |abruf=2018-06-24}}</ref><ref>{{Internetquelle |url=http://primes.utm.edu/primes/lists/short.txt |titel=Liste der größten bekannten Primzahlen |sprache=en |abruf=2018-06-21}}</ref>|| Primzahl <math>p</math> || Dezimalstellen<br /> von <math>p</math> || Entdeckungsdatum || Entdecker || Quelle
|-
|style="text-align:right"| 1
|style="text-align:center"| 1958.
|style="text-align:right"| <math>2618163402417 \cdot 2^{1290001}-1</math>
|style="text-align:center"| <math>388342</math>
|style="text-align:right"| 29. Februar 2016
| Scott Brown ([[Vereinigte Staaten|USA]])
|style=text-align:center |<ref>[http://primes.utm.edu/primes/page.php?id=121331 Sophie-Germain-Zahl 2618163402417·2<sup>1290001</sup> - 1] auf Prime Pages</ref>
|-
|style="text-align:right"| 2
|style="text-align:center"| 2001.
|style="text-align:right"| <math>18543637900515 \cdot 2^{666668}-1</math>
|style="text-align:center"| <math>200701</math>
|style="text-align:right"| 4. oder 9. April 2012
| Lee Blyth ([[Australien|AUS]])
|style=text-align:center |<ref>[http://primes.utm.edu/primes/page.php?id=106227 Sophie-Germain-Zahl 18543637900515·2<sup>666668</sup> - 1] auf Prime Pages</ref>
|-
|style="text-align:right"| 3
|style="text-align:center"| 2018.
|style="text-align:right"| <math>183027 \cdot 2^{265441}-1</math>
|style="text-align:center"| <math>79911</math>
|style="text-align:right"| 22. März 2010
| Tom Wu
|style=text-align:center |<ref>[http://primes.utm.edu/primes/page.php?id=92223 Sophie-Germain-Zahl 183027·2<sup>265441</sup> - 1] auf Prime Pages</ref>
|-
|style="text-align:right"| 4
|style="text-align:center"| 2027.
|style="text-align:right"| <math>648621027630345 \cdot 2^{253825}-1</math>
|style="text-align:center"| <math>76424</math>
|style="text-align:right"| 18. November 2009
| Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai
|style=text-align:center |<ref>[http://primes.utm.edu/primes/page.php?id=90908 Sophie-Germain-Zahl 648621027630345·2<sup>253825</sup> - 1] auf Prime Pages</ref>
|-
|style="text-align:right"| 5
|style="text-align:center"| 2028.
|style="text-align:right"| <math>620366307356565 \cdot 2^{253825}-1</math>
|style="text-align:center"| <math>76424</math>
|style="text-align:right"| 2. November 2009
| Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai
|style=text-align:center |<ref>[http://primes.utm.edu/primes/page.php?id=90710 Sophie-Germain-Zahl 620366307356565·2<sup>253825</sup> - 1] auf Prime Pages</ref>
|-
|style="text-align:right"| 6
|style="text-align:center"| 2048.
|style="text-align:right"| <math>1068669447 \cdot 2^{211088}-1</math>
|style="text-align:center"| <math>63553</math>
|style="text-align:right"| 17. Mai 2020
| Michael Kwok
|style=text-align:center |<ref>[https://primes.utm.edu/primes/page.php?id=130903 Sophie-Germain-Zahl 1068669447 · 2<sup>211088</sup> - 1] auf Prime Pages</ref>
|-
|style="text-align:right"| 7
|style="text-align:center"| 2055.
|style="text-align:right"| <math>99064503957 \cdot 2^{200009}-1</math>
|style="text-align:center"| <math>60220</math>
|style="text-align:right"| 1. April 2016
| S. Urushihata
|style=text-align:center |<ref>[http://primes.utm.edu/primes/page.php?id=121508 Sophie-Germain-Zahl 99064503957·2<sup>200009</sup> - 1] auf Prime Pages</ref>
|-
|style="text-align:right"| 8
|style="text-align:center"| 2072.
|style="text-align:right"| <math>12443794755 \cdot 2^{184516}-1</math>
|style="text-align:center"| <math>55555</math>
|style="text-align:right"| 9. September 2021
| Serge Batalov
|style=text-align:center |<ref>[https://primes.utm.edu/primes/page.php?id=132701 Sophie-Germain-Zahl 12443794755·2<sup>184516</sup> - 1] auf Prime Pages</ref>
|-
|style="text-align:right"| 9
|style="text-align:center"| 2073.
|style="text-align:right"| <math>21749869755 \cdot 2^{184515}-1</math>
|style="text-align:center"| <math>55555</math>
|style="text-align:right"| 9. September 2021
| Serge Batalov
|style=text-align:center |<ref>[https://primes.utm.edu/primes/page.php?id=132699 Sophie-Germain-Zahl 21749869755·2<sup>184515</sup> - 1] auf Prime Pages</ref>
|-
|style="text-align:right"| 10
|style="text-align:center"| 2074.
|style="text-align:right"| <math>14901867165 \cdot 2^{184515}-1</math>
|style="text-align:center"| <math>55555</math>
|style="text-align:right"| 9. September 2021
| Serge Batalov
|style=text-align:center |<ref>[https://primes.utm.edu/primes/page.php?id=132697 Sophie-Germain-Zahl 14901867165·2<sup>184515</sup> - 1] auf Prime Pages</ref>
|}
{{FNBox|
  {{FNZ|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 <math>q = 7</math> haben alle sicheren Primzahlen die Form <math>q = 6k+5</math> mit einer ganzen Zahl <math>k \in \mathbb N</math>.
: Mit anderen Worten: <math>q \equiv 5 \pmod 6</math>.
:: '''Beweis:'''
::: Alle Zahlen der Restklassen <math>n \equiv 0 \pmod 6</math> oder <math>n \equiv 2 \pmod 6</math> oder <math>n \equiv 4 \pmod 6</math> sind gerade und demnach durch <math>2</math> teilbar.
::: Die Sophie-Germain-Primzahl <math>p = 2</math> führt auf die sichere Primzahl <math>q = 2 \cdot 2+1=5</math> und diese erfüllt die Bedingung <math>q \equiv 5 \pmod 6</math>.
::: Alle Zahlen der Restklassen <math>n \equiv 0 \pmod 6</math> oder <math>n \equiv 3 \pmod 6</math> sind durch <math>3</math> teilbar.
::: Die Sophie-Germain-Primzahl <math>p = 3</math> führt auf die sichere Primzahl <math>q = 2 \cdot 3+1=7</math> und diese erfüllt die Bedingung <math>q \equiv 5 \pmod 6</math> nicht, ist aber aus dieser Behauptung ohnehin ausgenommen.
::: Zwar existieren Primzahlen in der Restklasse <math>p \equiv 1 \pmod 6</math>, jedoch würde man dadurch wegen <math>q=2p+1=2 \cdot (6n+1)+1 = 12n+3 = 3 \cdot (4n+1)</math> sichere „Primzahlen“ erhalten, die durch <math>3</math> teilbar wären und somit keine Primzahlen sein können.
::: Als einzige Sechser-Restklasse für sichere Primzahlen <math>q</math> bleibt somit die Restklasse <math>q \equiv 5 \pmod 6</math> übrig. <math>\Box</math>
* Mit Ausnahme der sicheren Primzahl <math>q = 5</math> haben alle sicheren Primzahlen die Form <math>q = 4k+3</math> mit einer ganzen Zahl <math>k \in \mathbb N</math>.
: Mit anderen Worten: <math>q \equiv 3 \pmod 4</math>.
:: '''Beweis: '''
::: Bis auf die erste Sophie-Germain-Primzahl <math>p = 2</math> (welche auf die sichere Primzahl <math>q=2 \cdot 2+1=5</math> führt und für die diese Behauptung nicht stimmt) sind alle anderen Primzahlen ungerade, haben also die Form <math>p = 2n+1</math> mit <math>n \in \mathbb N</math>. Jede sichere Primzahl hat somit die Form <math>q = 2p+1=2 (2n+1)+1=4n+3</math>, was zu zeigen war. <math>\Box</math>
* Mit Ausnahme der sicheren Primzahlen <math>q = 5</math> und <math>q = 7</math> haben alle sicheren Primzahlen die Form <math>q = 12k+11</math> mit einer ganzen Zahl <math>k \in \mathbb N</math>.
: Mit anderen Worten: <math>q \equiv 11 \pmod {12}</math>.
:: '''Beweis: '''
::: Alle Sophie-Germain-Primzahlen <math>p>3</math> führen auf die sicheren Primzahlen <math>q=2p+1>2 \cdot 3+1=7</math> und haben die Form <math>p=6k+5</math> (siehe [[Sophie-Germain-Primzahl#Bedeutung|Beweis]]). Somit gilt für die sichere Primzahl <math>q=2p+1=2 \cdot (6k+5)+1=12k+11</math>, was zu zeigen war. <math>\Box</math>
* Für alle sicheren Primzahlen <math>q>7</math> gilt:
:: <math>3</math> ist ein [[quadratischer Rest]] modulo <math>q</math>.
:: '''Beweis: '''
::: Sichere Primzahlen haben die Form <math>q=2p+1</math> mit <math>p \in \mathbb P</math>. Wegen der Voraussetzung <math>q>7=2p+1</math> ist <math>p>3</math>. (Ungerade) Primzahlen <math>p>3</math> erfüllen aber die Kongruenz <math>p \equiv 1 \pmod 6</math> oder <math>p \equiv 5 \pmod 6</math>, weil alle ungeraden Zahlen der Form <math>n \equiv 3 \pmod 6</math> durch <math>3</math> teilbar sind. Primzahlen der Form <math>p \equiv 1 \pmod 6</math> können keine [[Sophie-Germain-Primzahl]]en sein, weil dann <math>q=2p+1 \equiv 2 \cdot 1+1 = 3 \pmod 6</math> durch <math>3</math> teilbar wäre und somit keine sicheren Primzahlen sind. Es bleibt nur <math>p \equiv 5 \pmod 6</math> übrig, also ist <math>p \equiv 5 \pmod {12}</math> oder <math>p \equiv 5+6=11 \pmod {12}</math>. Somit ist in beiden Fällen <math>q=2p+1 \equiv 2 \cdot 5+1 \equiv 2 \cdot 11+1=23 \equiv 11 \pmod {12}</math>. Es gibt aber den mathematischen [[Satz (Mathematik)|Satz]], dass <math>3</math> ein quadratischer Rest modulo <math>q</math> ist, [[genau dann, wenn]] <math>q \equiv 1 \pmod {12}</math> oder <math>q \equiv -1 \equiv 11 \pmod {12}</math> ist.<ref>{{Internetquelle
| hrsg    = The [[Internationale Mathematik-Olympiade|IMO]] Compendium Group
| autor   = Dušan Djukić
| url     = https://web.math.pmf.unizg.hr/nastava/studnatj/quadcong_ddj.pdf
| titel   = Quadratic Congruences
| titelerg= Theorem 10c
| seiten  = 1–12
| datum   = 2007
| zugriff = 2020-03-17
}}</ref> Somit ist <math>3</math> ein [[quadratischer Rest]] modulo <math>q</math>, was zu zeigen war. <math>\Box</math>
* Für alle sicheren Primzahlen <math>q>7</math> gilt:
:: <math>q</math> teilt <math>3^{\frac{q-1}{2}}-1</math>.
:: '''Beweis: '''
::: Weil <math>3</math> ein quadratischer Rest modulo <math>q</math> ist, gilt [[Quadratischer Rest#Quadratische Reste bei Primzahlmoduln|folgende Kongruenz]]: <math>3^{\frac{q-1}{2}} \equiv 1 \pmod q</math>. Daraus folgt direkt, dass <math>q</math> ein Teiler von <math>3^{\frac{q-1}{2}}-1</math> ist. <math>\Box</math>
* Sei <math>q \equiv 7 \pmod 8</math> eine sichere Primzahl. Dann gilt:
:: <math>q</math> ist Teiler derjenigen [[Mersenne-Zahl]], dessen [[Potenz (Mathematik)|Exponent]] die dazugehörige Sophie-Germain-Primzahl ist.
:: Mit anderen Worten: <math>q</math> teilt <math>M_{p}</math> mit <math>p=\frac{q-1}{2}</math>
: (siehe auch [[Mersenne-Zahl#Teilbarkeitseigenschaften der Mersenne-Zahlen|Teilbarkeitseigenschaften der Mersenne-Zahlen]])
:: '''Beispiel: '''
::: Es ist <math>q=23 \equiv 7 \pmod 8</math>. Dann ist die dazugehörige Sophie-Germain-Primzahl <math>p=\frac{23-1}{2}=11</math>.
::: Tatsächlich ist <math>q=23</math> Teiler von <math>M_{11}=2^{11}-1=2048-1=2047 = 23 \cdot 89</math>.
* Es gibt mit Ausnahme der Primzahl <math>q=5</math> keine [[Fermat-Zahl|Fermat-Primzahlen]], welche gleichzeitig sichere Primzahlen sind.
:: '''Beweis: '''
::: Fermat-Primzahlen sind von der Form <math>F=q=2^n+1</math>. Daraus folgt, dass <math>\frac{F-1}{2}=\frac{q-1}{2}=p=2^{n-1}</math> eine Zweierpotenz, aber keine (Sophie-Germain-)Primzahl ist (außer für <math>p=2^1</math> und somit für <math>q=2 \cdot 2+1=5</math>). Somit kann die Fermat-Primzahl <math>F</math> keine sichere Zahl sein, was zu beweisen war. <math>\Box</math>
* Es gibt mit Ausnahme der Primzahl <math>q=7</math> keine [[Mersenne-Zahl|Mersenne-Primzahlen]], welche gleichzeitig sichere Primzahlen sind.
:: '''Beweis: '''
::: Weiter oben wurde bewiesen, dass alle sicheren Primzahlen mit Ausnahme von <math>q=7</math> die Form <math>q=6k_2+5=6(k_2+1)-1=:6k-1</math> haben. Mersenne-Primzahlen sind von der Form <math>p=2^m-1</math>. Somit müsste <math>2^m-1=6k-1</math> sein und deswegen wäre <math>2^m=6k</math>. <math>2^m</math> ist aber niemals durch <math>6</math> teilbar, woraus folgt, dass niemals eine Mersenne-Primzahl gleichzeitig eine sichere Primzahl sein darf (mit Ausnahme von <math>q=7=2^3-1</math>). <math>\Box</math>
* 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: <math>a_0=p</math> (also eine Sophie-Germain-Primzahl), alle weiteren Folgenglieder haben die Form <math>a_{n+1}=2 \cdot a_n+1</math> und sind somit laut Definition sichere Primzahlen. <math>\Box</math>
* Sei <math>q</math> eine sichere Primzahl der Form <math>q=10k+7</math> (sie soll also mit <math>7</math> enden), welche in einer Cunningham-Kette vorkommt. Dann gilt:
:: Die Zahl <math>q</math> beendet die Cunningham-Kette, sie ist also das letzte Folgenglied dieser Kette.
:: '''Beweis: '''
::: Das nächste Folgenglied dieser Kette wäre <math>2 \cdot (10k+7)+1=20k+15=5 \cdot (4k+3)</math> und wäre somit durch <math>5</math> teilbar und deswegen keine Primzahl mehr. <math>\Box</math>
* Sei <math>p \in \mathbb P</math> eine Primzahl. Dann gilt:<ref>{{Internetquelle |autor=Chris K. Caldwell |url=https://primes.utm.edu/notes/proofs/MerDiv2.html |titel=Proof of a result of Euler and Lagrange on Mersenne Divisors |hrsg=Prime Pages |abruf=2019-08-14}}</ref><ref>{{Internetquelle |autor=Henri Lifchitz |url=http://www.primenumbers.net/Henri/us/NouvTh1us.htm |titel=Generalization of Euler-Lagrange theorem and new primality tests |abruf=2019-08-14}}</ref>
:: Ist <math>p \equiv 1 \pmod{4}</math>, dann gilt:
::: <math>q=2p+1</math> ist eine sichere Primzahl [[genau dann, wenn]] <math>q=2p+1</math> Teiler von <math>2^p+1</math> ist
:: Ist <math>p \equiv 3 \pmod{4}</math>, dann gilt:
::: <math>q=2p+1</math> ist eine sichere Primzahl genau dann, wenn <math>q=2p+1</math> Teiler von <math>2^p-1</math> ist

== Weblinks ==
* {{MathWorld |id= SophieGermainPrime|title= Sophie Germain Prime}}
* {{PlanetMath |id=SafePrime |title=Safe Prime}}

== Einzelnachweise ==
<references />

{{Navigationsleiste Primzahlklassen}}

[[Kategorie:Ganzzahlmenge]]
[[Kategorie:Primzahl]]
[[Kategorie:Zahlentheorie]]