Starke Primzahl

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 | Quelltext 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: .

  • 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)
  • 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 .

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 .

Einzelnachweise

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