Starke Primzahl

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

Definition in der Zahlentheorie

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

Beispiele

• Die Primzahl $p_7=17$ ist die siebente Primzahl. Die nächstkleinere, die sechste Primzahl, ist $p_6=13$, die nächstgrößere, die achte Primzahl, ist $p_8=19$. Das arithmetische Mittel von $p_6$ und $p_8$ ist $\frac{p_6+p_8}{2}=\frac{13+19}{2}=\frac{32}{2}=16$. Es ist offensichtlich $p_7=17>16$, somit ist $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, … (Vorlage:OEIS)

Eigenschaften

• 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. $◻$

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

Beweis:

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

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

Definition in der Kryptographie

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

• $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:

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

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

• $q_1-1$ hat „große“ Primfaktoren.

Das heißt, $q_1-1=a_2\cdot q_2$ mit $a_2\in \mathbb{N}$ und einer großen Primzahl $q_2$.

• $p+1$ hat „große“ Primfaktoren.

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

Anwendung in der Kryptographie

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

Beispiel für eine starke Primzahl im zahlentheoretischen und kryptographischen Sinn

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:

$p_n=439351292910452432574786963588089477522344331\in \mathbb{P}$

Die nächstkleinere Primzahl ist

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

Die nächstgrößere Primzahl ist

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

Somit gilt für das arithmetische Mittel

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

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

Die Primfaktorisierung der Zahl $p_n-1$ lautet:

$p_n-1=439351292910452432574786963588089477522344330=2\cdot 5\cdot 281\cdot 3463\cdot 25831859679582977\cdot 1747822896920092227343=a_1\cdot q_1$

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

Die Primfaktorisierung der Zahl $q_1-1$ lautet:

$q_1-1=1747822896920092227342=2\cdot 3\cdot 173\cdot 1683837087591611009=a_2\cdot q_2$

Es ist wie verlangt $q_1-1=a_2\cdot q_2$ mit $a_2\in \mathbb{N}$ und ausreichend großem $q_2=1683837087591611009\in \mathbb{P}$

Die Primfaktorisierung der Zahl $p_n+1$ lautet:

$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 $p+1=a_3\cdot q_3$ mit $a_3\in \mathbb{N}$ und ausreichend großem $q_3=864608136454559457049\in \mathbb{P}$

Somit erfüllt die Zahl $p_n$ auch die kryptographische Definition von starken Primzahlen.

Wohlgemerkt: diese in beiden Definitionen starke Primzahl $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 $p_n$.

Bezeichnungen

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

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

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

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

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

• Ist $p_n<\frac{p_{n-1}+p_{n+1}}{2}$, so nennt man $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 $p_{n-1}$ als an der nächsten Primzahl $p_{n+1}$.

Siehe auch

• Sichere Primzahl

Weblinks

• Vorlage:Internetquelle
• Vorlage:PlanetMath
• Lenstra elliptic-curve factorization (en)
• Strong cryptography (en)