Starke Primzahl

Eine starke Primzahl (vom englischen strong prime) ist eine ganze Zahl ${\displaystyle p\in \mathbb {N} }$ mit gewissen Eigenschaften, die allerdings je nach Betrachtungsweise in der Kryptographie bzw. in der Zahlentheorie unterschiedlich sind.

In der Zahlentheorie ist eine starke Primzahl im zahlentheoretischen Sinn eine ganze Zahl ${\displaystyle p_{n}\in \mathbb {P} }$, welche größer ist als das arithmetische Mittel ihrer nächstkleineren Primzahl ${\displaystyle p_{n-1}\in \mathbb {P} }$ und ihrer nächstgrößeren Primzahl ${\displaystyle p_{n+1}\in \mathbb {P} }$. Mit anderen Worten: ${\displaystyle p_{n}>{\frac {p_{n-1}+p_{n+1}}{2}}}$.

• Die Primzahl ${\displaystyle p_{7}=17}$ ist die siebente Primzahl. Die nächstkleinere, die sechste Primzahl, ist ${\displaystyle p_{6}=13}$, die nächstgrößere, die achte Primzahl, ist ${\displaystyle p_{8}=19}$. Das arithmetische Mittel von ${\displaystyle p_{6}}$ und ${\displaystyle p_{8}}$ ist ${\displaystyle {\frac {p_{6}+p_{8}}{2}}={\frac {13+19}{2}}={\frac {32}{2}}=16}$. Es ist offensichtlich ${\displaystyle p_{7}=17>16}$, somit ist ${\displaystyle 17}$ eine starke Primzahl.
• Die kleinsten starken Primzahlen im zahlentheoretischen Sinn sind die folgenden:

11, 17, 29, 37, 41, 59, 67, 71, 79, 97, 101, 107, 127, 137, 149, 163, 179, 191, 197, 223, 227, 239, 251, 269, 277, 281, 307, 311, 331, 347, 367, 379, 397, 419, 431, 439, 457, 461, 479, 487, 499, 521, 541, 557, 569, 587, 599, … (Folge A051634 in OEIS)

• Eine starke Primzahl im zahlentheoretischen Sinn liegt näher an der nächsthöheren Primzahl als an der nächstkleineren Primzahl.

Beweis:

Diese Eigenschaft resultiert aus der Definition, dass eine starke Primzahl größer sein muss als das arithmetische Mittel ihrer primen Nachbarn. ${\displaystyle \Box }$

• Bei Primzahlzwillingen ${\displaystyle (p,p+2)}$ mit ${\displaystyle p>5}$ gilt: ${\displaystyle p}$ ist eine starke Primzahl.

Beweis:

Es gibt keine Primzahldrillinge der Form ${\displaystyle (p-2,p,p+2)}$, weil die Zahl ${\displaystyle 3}$ mindestens einen dieser drei Zahlen teilen muss. Wenn ${\displaystyle p}$ und ${\displaystyle p+2}$ Primzahlen sind, muss ${\displaystyle 3}$ die Zahl ${\displaystyle p-2}$ teilen. Somit ist ${\displaystyle p-2}$ nicht prim. Somit ist die nächstkleinere Primzahl von ${\displaystyle p}$ nicht ${\displaystyle p-2}$, sondern maximal ${\displaystyle p-4}$. Für das arithmetische Mittel der Primnachbarn von ${\displaystyle p}$ gilt also ${\displaystyle {\frac {p_{n-1}+p_{n+1}}{2}}\leq {\frac {p-4+p+2}{2}}={\frac {2p-2}{2}}=p-1<p}$, womit die Definition für starke Primzahlen erfüllt ist. ${\displaystyle \Box }$

• Die einzigen Primzahlzwillinge ${\displaystyle (p,p+2)}$, bei denen ${\displaystyle p}$ keine starke Primzahl ist, sind die Paare ${\displaystyle (3,5)}$ und ${\displaystyle (5,7)}$ (resultiert aus oberer Eigenschaft).

In der Kryptographie ist eine starke Primzahl im kryptographischen Sinn eine ganze Zahl ${\displaystyle p\in \mathbb {P} }$, wenn sie folgende Eigenschaften erfüllt:^[1]

• ${\displaystyle p}$ kann nicht mit der Pollard-p-1-Methode in einer angemessenen Zeit faktorisiert werden (sie sind aber möglicherweise trotzdem mit anderen Methoden, wie zum Beispiel der Faktorisierung mit elliptischen Kurven von Lenstra (ECM) angreifbar, also faktorisierbar).

Mit anderen Worten soll eine starke Primzahl im kryptographischen Sinn folgende Bedingungen erfüllen:

• ${\displaystyle p}$ ist ausreichend groß, damit man sie in der Kryptographie verwenden kann. Kryptoanalysten sollten wegen der „Größe“ von ${\displaystyle p}$ nicht in der Lage sein, sie zu faktorisieren (sie also in ihre Primteiler zu zerlegen).
• ${\displaystyle p-1}$ hat „große“ Primfaktoren.

Das heißt, ${\displaystyle p-1=a_{1}\cdot q_{1}}$ mit ${\displaystyle a_{1}\in \mathbb {N} }$ und einer großen Primzahl ${\displaystyle q_{1}}$.

• ${\displaystyle q_{1}-1}$ hat „große“ Primfaktoren.

Das heißt, ${\displaystyle q_{1}-1=a_{2}\cdot q_{2}}$ mit ${\displaystyle a_{2}\in \mathbb {N} }$ und einer großen Primzahl ${\displaystyle q_{2}}$.

• ${\displaystyle p+1}$ hat „große“ Primfaktoren.

Das heißt, ${\displaystyle p+1=a_{3}\cdot q_{3}}$ mit ${\displaystyle a_{3}\in \mathbb {N} }$ und einer großen Primzahl ${\displaystyle q_{3}}$.

Bei der Schlüsselerzeugung in RSA-Kryptosystemen sollte der Modul ${\displaystyle n}$ als Produkt von zwei starken Primzahlen ${\displaystyle p}$ und ${\displaystyle q}$ verwendet werden (siehe Erzeugung des öffentlichen und privaten Schlüssels). Diese Methode macht die Faktorisierung der so erhaltenen zusammengesetzten Zahl ${\displaystyle n=p\cdot q}$ zum Beispiel mit der Pollard-p-1-Methode undurchführbar.^[1][2]

Es gibt starke Primzahlen, die beide Definitionen, also die im zahlentheoretischen Sinn und die im kryptographischen Sinn erfüllen. Die folgende Zahl erfüllt beide Definitionen:^[1]

${\displaystyle p_{n}=439351292910452432574786963588089477522344331\in \mathbb {P} }$

Die nächstkleinere Primzahl ist

${\displaystyle p_{n-1}=p_{n}-132=439351292910452432574786963588089477522344199\in \mathbb {P} }$

Die nächstgrößere Primzahl ist

${\displaystyle p_{n+1}=p_{n}+8=439351292910452432574786963588089477522344339\in \mathbb {P} }$

Somit gilt für das arithmetische Mittel

${\displaystyle p_{n}>{\frac {p_{n-1}+p_{n+1}}{2}}=439351292910452432574786963588089477522344269}$

Die Zahl ${\displaystyle p_{n}}$ ist um ${\displaystyle 62}$ größer als das arithmetische Mittel ihrer primen Nachbarn ${\displaystyle p_{n-1}}$ und ${\displaystyle p_{n+1}}$, somit erfüllt sie die zahlentheoretische Definition von starken Primzahlen.

Die Primfaktorisierung der Zahl ${\displaystyle p_{n}-1}$ lautet:

${\displaystyle p_{n}-1=439351292910452432574786963588089477522344330=2\cdot 5\cdot 281\cdot 3463\cdot 25831859679582977\cdot 1747822896920092227343=a_{1}\cdot q_{1}}$

Es ist wie verlangt ${\displaystyle p-1=a_{1}\cdot q_{1}}$ mit ${\displaystyle a_{1}\in \mathbb {N} }$ und ausreichend großem ${\displaystyle q_{1}=1747822896920092227343\in \mathbb {P} }$

Die Primfaktorisierung der Zahl ${\displaystyle q_{1}-1}$ lautet:

${\displaystyle q_{1}-1=1747822896920092227342=2\cdot 3\cdot 173\cdot 1683837087591611009=a_{2}\cdot q_{2}}$

Es ist wie verlangt ${\displaystyle q_{1}-1=a_{2}\cdot q_{2}}$ mit ${\displaystyle a_{2}\in \mathbb {N} }$ und ausreichend großem ${\displaystyle q_{2}=1683837087591611009\in \mathbb {P} }$

Die Primfaktorisierung der Zahl ${\displaystyle p_{n}+1}$ lautet:

${\displaystyle p_{n}+1=439351292910452432574786963588089477522344332=2^{2}\cdot 3^{2}\cdot 7691\cdot 352463\cdot 5207073944711\cdot 864608136454559457049=a_{3}\cdot q_{3}}$

Es ist wie verlangt ${\displaystyle p+1=a_{3}\cdot q_{3}}$ mit ${\displaystyle a_{3}\in \mathbb {N} }$ und ausreichend großem ${\displaystyle q_{3}=864608136454559457049\in \mathbb {P} }$

Somit erfüllt die Zahl ${\displaystyle p_{n}}$ auch die kryptographische Definition von starken Primzahlen.

Wohlgemerkt: diese in beiden Definitionen starke Primzahl ${\displaystyle p_{n}}$ erfüllt die kryptographische Definition, wenn man Faktorisierungsalgorithmen erlaubt, die durchaus fortschrittlicher sein dürfen als die Probedivision, solange man mit der Hand rechnet. Moderne Computeralgebrasysteme faktorisieren obige Zahlen in Sekundenbruchteilen. Eine momentan starke Primzahl im kryptographischen Sinn muss viel größer sein als obige Zahl ${\displaystyle p_{n}}$.

Vergleicht man eine Primzahl ${\displaystyle p_{n}}$ mit dem arithmetischen Mittel ${\displaystyle {\frac {p_{n-1}+p_{n+1}}{2}}}$ ihrer Primnachbarn ${\displaystyle p_{n-1}}$ und ${\displaystyle p_{n+1}}$, so erhält man folgende Typen:

• Ist ${\displaystyle p_{n}>{\frac {p_{n-1}+p_{n+1}}{2}}}$, so nennt man ${\displaystyle p_{n}}$ starke Primzahl.

Sie liegt näher an der nächsten Primzahl ${\displaystyle p_{n+1}}$ als an der vorherigen Primzahl ${\displaystyle p_{n-1}}$.

• Ist ${\displaystyle p_{n}={\frac {p_{n-1}+p_{n+1}}{2}}}$, so nennt man ${\displaystyle p_{n}}$ ausbalancierte Primzahl (vom englischen balanced prime).

Sie liegt exakt zwischen der nächsten Primzahl ${\displaystyle p_{n+1}}$ und der vorherigen Primzahl ${\displaystyle p_{n-1}}$.

• Ist ${\displaystyle p_{n}<{\frac {p_{n-1}+p_{n+1}}{2}}}$, so nennt man ${\displaystyle p_{n}}$ schwache Primzahl (vom englischen weak prime, nicht zu verwechseln mit dem namensgleichen Begriff „schwache Primzahl“ (vom englischen weakly prime number)).

Sie liegt näher an der vorherigen Primzahl ${\displaystyle p_{n-1}}$ als an der nächsten Primzahl ${\displaystyle p_{n+1}}$.

• Sichere Primzahl

1. ↑ ^{a b c} Strong Prime. In: PlanetMath. (englisch)
2. ↑ Ron Rivest, Robert Silverman: Are 'Strong' Primes Needed for RSA. Cryptology ePrint Archive: Report 2001/007, abgerufen am 24. Juni 2018. 

• Alexander W. Dent, Chris J. Mitchell: A Companion to User’s Guide to Cryptography and Standards. Abgerufen am 27. Mai 2018 (englisch). 
• Strong Prime. In: PlanetMath. (englisch)
• Lenstra elliptic-curve factorization (en)
• Strong cryptography (en)