Sichere Primzahl
# 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.

## 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⁠ | Primzahl $p$ | Dezimalstellen von $p$ | Entdeckungsdatum | Entdecker |
| - | - | - | - | - | - |
| 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{\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. 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:

       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
