Starke Primzahl

Unterklasse von Primzahlen

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

Definition in der Zahlentheorie

Bearbeiten

In der Zahlentheorie ist eine starke Primzahl im zahlentheoretischen Sinn eine ganze Zahl  , welche größer ist als das arithmetische Mittel ihrer nächstkleineren Primzahl   und ihrer nächstgrößeren Primzahl  . Mit anderen Worten:  .

Beispiele

Bearbeiten
  • Die Primzahl   ist die siebente Primzahl. Die nächstkleinere, die sechste Primzahl, ist  , die nächstgrößere, die achte Primzahl, ist  . Das arithmetische Mittel von   und   ist  . Es ist offensichtlich  , somit ist   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)

Eigenschaften

Bearbeiten
  • 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   mit   gilt:   ist eine starke Primzahl.
Beweis:
Es gibt keine Primzahldrillinge der Form  , weil die Zahl   mindestens einen dieser drei Zahlen teilen muss. Wenn   und   Primzahlen sind, muss   die Zahl   teilen. Somit ist   nicht prim. Somit ist die nächstkleinere Primzahl von   nicht  , sondern maximal  . Für das arithmetische Mittel der Primnachbarn von   gilt also  , womit die Definition für starke Primzahlen erfüllt ist.  
  • Die einzigen Primzahlzwillinge  , bei denen   keine starke Primzahl ist, sind die Paare   und   (resultiert aus oberer Eigenschaft).

Definition in der Kryptographie

Bearbeiten

In der Kryptographie ist eine starke Primzahl im kryptographischen Sinn eine ganze Zahl  , wenn sie folgende Eigenschaften erfüllt:[1]

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

  •   ist ausreichend groß, damit man sie in der Kryptographie verwenden kann. Kryptoanalysten sollten wegen der „Größe“ von   nicht in der Lage sein, sie zu faktorisieren (sie also in ihre Primteiler zu zerlegen).
  •   hat „große“ Primfaktoren.
Das heißt,   mit   und einer großen Primzahl  .
  •   hat „große“ Primfaktoren.
Das heißt,   mit   und einer großen Primzahl  .
  •   hat „große“ Primfaktoren.
Das heißt,   mit   und einer großen Primzahl  .

Anwendung in der Kryptographie

Bearbeiten

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

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

Bearbeiten

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]

 

Die nächstkleinere Primzahl ist

 

Die nächstgrößere Primzahl ist

 

Somit gilt für das arithmetische Mittel

 

Die Zahl   ist um   größer als das arithmetische Mittel ihrer primen Nachbarn   und  , somit erfüllt sie die zahlentheoretische Definition von starken Primzahlen.

Die Primfaktorisierung der Zahl   lautet:

 

Es ist wie verlangt   mit   und ausreichend großem  

Die Primfaktorisierung der Zahl   lautet:

 

Es ist wie verlangt   mit   und ausreichend großem  

Die Primfaktorisierung der Zahl   lautet:

 

Es ist wie verlangt   mit   und ausreichend großem  

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

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

Bezeichnungen

Bearbeiten

Vergleicht man eine Primzahl   mit dem arithmetischen Mittel   ihrer Primnachbarn   und  , so erhält man folgende Typen:

  • Ist  , so nennt man   starke Primzahl.
Sie liegt näher an der nächsten Primzahl   als an der vorherigen Primzahl  .
  • Ist  , so nennt man   ausbalancierte Primzahl (vom englischen balanced prime).
Sie liegt exakt zwischen der nächsten Primzahl   und der vorherigen Primzahl  .
  • Ist  , so nennt man   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   als an der nächsten Primzahl  .

Siehe auch

Bearbeiten

Einzelnachweise

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