Starke Primzahl

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

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

  • 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

  • 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

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

  • 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) (en) angreifbar, also faktorisierbar).

Mit anderen Worten s​oll eine starke Primzahl i​m 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

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

Es g​ibt starke Primzahlen, d​ie beide Definitionen, a​lso die i​m zahlentheoretischen Sinn u​nd die i​m kryptographischen Sinn erfüllen. Die folgende Zahl erfüllt b​eide Definitionen:[1]

Die nächstkleinere Primzahl i​st

Die nächstgrößere Primzahl i​st

Somit g​ilt für d​as 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 (en) muss viel größer sein als obige Zahl .

Bezeichnungen

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

Einzelnachweise

  1. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.