Algorithmen zur Suche nach Primzahlen

„Die größte Primzahl ist 2 ^32582657 -1 . Und ich bestätige stolz, dass ich mich an alle seine Zahlen erinnert habe ... in binärer Form. "
Karl Pomerance

Eine natürliche Zahl heißt Primzahl, wenn sie nur zwei verschiedene Teiler hat: einen und sich selbst. Die Aufgabe, Primzahlen zu finden, verfolgt Mathematiker schon sehr lange. Dieses Problem hatte lange Zeit keine direkte praktische Anwendung, aber mit dem Aufkommen der Kryptographie mit öffentlichen Schlüsseln änderte sich alles. Dieser Artikel beschreibt verschiedene Möglichkeiten zur Suche nach Primzahlen, die sowohl von rein akademischem Interesse sind als auch heute in der Kryptographie verwendet werden.

Sieb von Eratosthenes

Sieb von Eratosthenes - ein Algorithmus, der vom antiken griechischen Mathematiker Eratosthenes vorgeschlagen wurde. Mit dieser Methode können Sie alle Primzahlen finden, die kleiner als eine bestimmte Zahl n sind . Das Wesentliche der Methode ist wie folgt. Betrachten wir eine Reihe von Zahlen von 2 bis n. Kreuzen Sie alle durch 2 teilbaren Zahlen mit Ausnahme von 2 an. Von der Menge (wir eliminieren) gehen wir zur nächsten „nicht eliminierten“ Zahl - 3, streichen Sie alles, was durch 3 teilbar ist, erneut durch. Wir gehen zur nächsten verbleibenden Zahl - 5 und so weiter, bis wir wir kommen zu n . Nach dem Ausführen der obigen Schritte verbleiben nur Primzahlen in der ursprünglichen Liste.

Der Algorithmus kann leicht optimiert werden. Da einer der Teiler der Anzahl n der zusammengesetzten erforderlich $$$\ leqslant \ sqrt {n}$ kann der Algorithmus nach dem Löschen der durch teilbaren Zahlen gestoppt werden $$$\ sqrt {n}$ .

Illustration der Funktionsweise des Algorithmus aus Wikipedia:


Die Komplexität des Algorithmus ist $$$O (n \ log \ log n)$ Gleichzeitig ist es erforderlich, Informationen darüber zu speichern, welche Nummern durchgestrichen wurden $$$O (n)$ Speicher.

Es gibt eine Reihe von Optimierungen, um diese Indikatoren zu reduzieren. Ein Trick, der als Radfaktorisierung bezeichnet wird, besteht darin, nur Zahlen in die ursprüngliche Liste aufzunehmen, die mit den ersten Primzahlen koprime sind (z. B. weniger als 30). Theoretisch wird vorgeschlagen, die ersten einfachen bis etwa zu nehmen $$$\ sqrt {\ log n}$ . Dies reduziert die Komplexität des Algorithmus in $$$\ log \ log n$ mal. Neben den Verbrauch von Speichern zu reduzieren verwendete sogenannte Segmentierung. Der anfängliche Satz von Zahlen ist in Größenabschnitte unterteilt $$$\ leqslant \ sqrt {n}$ und für jedes Segment wird das Eratosthenes-Sieb separat angewendet. Der Speicherverbrauch wird auf reduziert $$$O (\ sqrt {n})$ .

Atkin-Sieb

Ein besserer Algorithmus zum Sieben von zusammengesetzten Zahlen wurde von Atkin und Bershtein vorgeschlagen und als Atkin-Sieb bezeichnet . Diese Methode basiert auf den folgenden drei Eigenschaften von Primzahlen.

Eigenschaft 1

Wenn n eine positive Zahl ist, die kein Vielfaches des Quadrats einer Primzahl ist und so, dass $$$n \ äquiv. 1 (\ mod 4)$ . Dann ist n genau dann eine Primzahl, wenn die Anzahl der Wurzeln der Gleichung $$$4 x ^ 2 + y ^ 2 = n$ seltsam.

Eigenschaft 2

Wenn n eine positive Zahl ist, die kein Vielfaches des Quadrats einer Primzahl ist und so, dass $$$n \ equiv 1 (\ mod 6)$ . Dann ist n genau dann eine Primzahl, wenn die Anzahl der Wurzeln der Gleichung $$$3x ^ 2 + y ^ 2 = n$ seltsam.

Eigenschaft 3

Wenn n eine positive Zahl ist, die kein Vielfaches des Quadrats einer Primzahl ist und so, dass $$$N \ equiv 11 (\ mod 12)$ . Dann ist n genau dann eine Primzahl, wenn die Anzahl der Wurzeln der Gleichung $$$3x ^ 2-y ^ 2 = n$ seltsam.

Hinweise für diese Eigenschaften finden Sie in diesem Artikel .

In der Anfangsphase Siebes Atkin Algorithmus ist ein Array der Größe A n, gefüllt mit Nullen. Um Primzahlen zu bestimmen, alle $$$X, y <\ sqrt n$ . Für jedes solche Paar wird berechnet $$$4x ^ 2 + y ^ 2$ , $$$3x ^ 2 + y ^ 2$ , $$$3x ^ 2-y ^ 2$ und den Wert der Elemente des Arrays $$$A [4x ^ 2 + y ^ 2]$ , $$$A [3x ^ 2 + y ^ 2]$ , $$$A [3x ^ 2-y ^ 2]$ erhöht sich um eins. Am Ende des Algorithmus sind die Indizes aller Elemente des Arrays mit ungeraden Werten entweder Primzahlen oder Quadrate einer Primzahl. Im letzten Schritt des Algorithmus werden die Quadrate der im Satz verbleibenden Zahlen durchgestrichen.

Aus der Beschreibung des Algorithmus folgt, dass die rechnerische Komplexität des Atkin-Siebs und der Speicherverbrauch sind $$$O (n)$ . Bei Verwendung der Radfaktorisierung und -segmentierung wird die Komplexitätsschätzung des Algorithmus auf reduziert $$$O (n / \ log \ log n)$ und Speicherverbrauch bis zu $$$O (\ sqrt {n})$ .

Mersenne-Zahlen und Luke-Lemer-Test

Mit solchen Komplexitätsindikatoren kann natürlich auch das für Atkin optimierte Sieb nicht zur Suche nach wirklich großen Primzahlen verwendet werden. Glücklicherweise gibt es schnelle Tests, um zu überprüfen, ob eine bestimmte Zahl eine Primzahl ist. Im Gegensatz zu Siebalgorithmen sind solche Tests nicht für die Suche nach allen Primzahlen ausgelegt, sondern können nur mit einiger Wahrscheinlichkeit feststellen, ob eine bestimmte Zahl eine Primzahl ist.

Eine solche Testmethode ist der Luc-Lemer-Test . Dies ist ein deterministischer und bedingungsloser Test der Einfachheit. Dies bedeutet, dass das Bestehen des Tests die Einfachheit der Nummer garantiert. Leider ist der Test nur für Zahlen besonderer Art gedacht $$$2 ^ p-1$ wobei p eine natürliche Zahl ist. Solche Nummern werden Mersenne-Nummern genannt.

Der Luke-Lemer-Test behauptet, dass die Mersenne-Nummer $$$M_p = 2 ^ p-1$ prime genau dann, wenn p prime ist und $$$M_p$ teilt $$$(p-1)$ Mitglied der Sequenz $$$S_k$ rekursiv setzen: $$$S_1 = 4, S_k = S_ {k-1} ^ 2-2$ für $$$k> 1$ .

Für die Nummer $$$M_p$ p Bitlänge ist die rechnerische Komplexität des Algorithmus $$${\ displaystyle O (p ^ {3})}$ .

Aufgrund der Einfachheit und des Determinismus des Tests sind die größten bekannten Primzahlen Mersenne-Zahlen. Der größte bekannte Primzahl bisher - $$$2 ^ {82,589,933} -1$ Die Dezimalschreibweise besteht aus 24.862.048 Stellen. Sie können diese Schönheit hier bewundern.

Satz von Fermat und Miller-Rabin-Test

Es sind nicht viele Mersenne-Primzahlen bekannt, daher erfordert die Kryptographie mit öffentlichen Schlüsseln eine andere Methode zur Suche nach Primzahlen. Eine solche Methode ist der Fermat-Einfachheitstest . Es basiert auf Fermats kleinem Satz, der besagt, dass wenn n eine Primzahl ist, für jedes a , das nicht durch n teilbar ist, die Gleichheit gilt $$$A ^ {n-1} \ equiv 1 {\ PMOD {n}}$ . Der Beweis des Satzes ist auf Wikipedia zu finden.

Der Fermat-Einfachheitstest ist ein Wahrscheinlichkeitstest, der darin besteht, mehrere Werte von a aufzuzählen, wenn mindestens einer von ihnen die Ungleichung erfüllt $$$a ^ {n-1} \ not \ equiv 1 \ pmod n$ dann ist die Zahl n zusammengesetzt. Ansonsten ist n wahrscheinlich eine Primzahl. Je mehr Werte von a im Test verwendet werden, desto höher ist die Wahrscheinlichkeit, dass n eine Primzahl ist.

Leider gibt es zusammengesetzte Zahlen n für welchen Vergleich $$$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ gilt für alle eine wechselseitige Primzahl mit n . Solche Zahlen werden Carmichael-Zahlen genannt . Zusammengesetzte Zahlen, die den Fermat-Test erfolgreich bestehen, werden als pseudo-einfaches Fermat bezeichnet. Die Anzahl der pseudo-einfachen Fermat ist unendlich, daher ist der Fermat-Test nicht der zuverlässigste Weg, um Primzahlen zu bestimmen.

Miller-Rabin-Test

Zuverlässigere Ergebnisse können erzielt werden, indem der kleine Satz von Fermat und die Tatsache kombiniert werden, dass es für eine Primzahl p keine anderen Wurzeln der Gleichung gibt $$$x ^ 2 \ equiv 1 \ pmod p$ außer 1 und -1. Der Miller-Rabin-Test zählt mehrere Werte von a auf und überprüft, ob die folgenden Bedingungen erfüllt sind.

Sei p eine Primzahl und $$$p-1 = 2 ^ sd$ , dann gilt für jede mindestens eine der Bedingungen:

1. $$$a ^ {d} \ equiv \ pm1 {\ pmod {p}}$
2. Es gibt eine ganze Zahl r <s, so dass $$$a ^ {2 ^ {r} d} \ equiv -1 {\ pmod {p}}$

Nach dem Satz von Fermat $$$a ^ {p-1} \ equiv1 \ pmod p$ und seitdem $$$p-1 = 2 ^ sd$ aus der Eigenschaft der Wurzeln der Gleichung $$$x ^ 2 \ equiv 1 \ pmod p$ Daraus folgt, dass wenn wir eine solche finden, dass eine der Bedingungen nicht erfüllt ist, p eine zusammengesetzte Zahl ist. Wenn eine der Bedingungen erfüllt ist, wird die Zahl a nach Miller als Zeuge der Einfachheit der Zahl n bezeichnet , und die Zahl n selbst ist wahrscheinlich eine Primzahl.

Je mehr Zeugen der Einfachheit gefunden werden, desto höher ist die Wahrscheinlichkeit, dass n eine Primzahl ist. Nach Rabins Theorem beträgt die Wahrscheinlichkeit, dass eine zufällig ausgewählte Zahl a die Einfachheit der zusammengesetzten Zahl bezeugt, ungefähr $$$1/4$ .

Wenn wir also k Zufallszahlen a prüfen, dann die Wahrscheinlichkeit, die zusammengesetzte Zahl als Primzahl zu nehmen $$$\ ca. (1/4) ^ k$ .

Die Komplexität des Algorithmus $$$O (k \ log ^ 3p)$ Dabei ist k die Anzahl der Prüfungen.

Aufgrund seiner Geschwindigkeit und hohen Genauigkeit wird der Miller-Rabin-Test häufig bei der Suche nach Primzahlen verwendet. Bei der Überprüfung großer Zahlen auf Einfachheit verwenden viele moderne kryptografische Bibliotheken nur diesen Test, und wie Martin Albrecht in seiner Arbeit gezeigt hat , reicht dies nicht immer aus.

Er konnte solche zusammengesetzten Zahlen generieren, die den Einfachheitstest in den Bibliotheken OpenSSL, CryptLib, JavaScript Big Number und vielen anderen erfolgreich bestanden haben.

Luke Test und Baillie - PSW Test

Um Schwachstellen in Situationen zu vermeiden, in denen eine von einem Angreifer generierte zusammengesetzte Zahl als Primzahl dargestellt wird, schlägt Martin Albrecht die Verwendung des Baillie-PSW- Tests vor. Trotz der Tatsache, dass der Baillie-PSW-Test probabilistisch ist, wurden bisher keine Verbindungsnummern gefunden, die diesen Test erfolgreich bestehen. Für die Suche nach einer solchen Zahl im Jahr 1980 versprachen die Autoren des Algorithmus eine Belohnung von 30 US-Dollar. Der Preis wurde noch nicht beansprucht.

Eine Reihe von Forschern überprüfte alle Zahlen bis zu $$$2 ^ {64}$ und keine einzige Verbindungsnummer hat den Baillie-PSW-Test bestanden. Daher für Zahlen weniger $$$2 ^ {64}$ Der Test wird als deterministisch angesehen.

Der Kern des Tests besteht darin, die Anzahl während einer Ausfallzeit durch zwei verschiedene Methoden konsistent zu überprüfen. Eine dieser Methoden ist der oben bereits beschriebene Miller-Rabin-Test. Der zweite ist Lukes Test für starke Pseudo-Einfachheit .

Luke Starker Pseudo-Einfachheitstest

Luc - Sequenzen - Rekursive Sequenzpaaren $$$\ {U_ {n} (P, Q) \}, \ {V_ {n} (P, Q) \}$ beschrieben durch die Ausdrücke:

$$

$${\ displaystyle U_ {0} (P, Q) = 0, \ quad U_ {1} (P, Q) = 1, \ quad U_ {n + 2} (P, Q) = P \ cdot U_ {n +1} (P, Q) -Q \ cdot U_ {n} (P, Q), \, n \ geq 0}$$

$$

$${\ displaystyle V_ {0} (P, Q) = 2, \ quad V_ {1} (P, Q) = P, \ quad V_ {n + 2} (P, Q) = P \ cdot V_ {n +1} (P, Q) -Q \ cdot V_ {n} (P, Q), \, n \ geq 0}$$

Lass $$$U_n (P, Q)$ und $$$V_n (P, Q)$ - Luc-Sequenz, wo die ganzen Zahlen P und Q die Bedingung $$${\ displaystyle D = P ^ {2} -4Q \ neq 0}$

Wir berechnen das Jacobi-Symbol : $$$\ left ({\ frac {D} {p}} \ right) = \ varepsilon$ .

Finden Sie solche r, s, für die die Gleichheit $$$n-ε = 2 ^ rs$

Für Primzahl n gilt eine der folgenden Bedingungen:

1. n teilt $$$U_s$
2. n teilt $$$V_ {2 ^ js}$ für einige j <r

Ansonsten ist n zusammengesetzt.

Die Wahrscheinlichkeit, dass eine zusammengesetzte Zahl n den Luc-Test für ein gegebenes Parameterpaar P, Q erfolgreich besteht, überschreitet 4/15 nicht. Daher ist diese Wahrscheinlichkeit nach k- maliger Anwendung des Tests $$$(4/15) ^ k$ .

Die Miller-Rabin- und Luke-Tests erzeugen disjunkte Sätze von pseudo-einfachen Zahlen. Wenn die Zahl p beide Tests bestanden hat, ist dies einfach. Auf dieser Eigenschaft basiert der Baillie-PSW-Test.

Fazit

Je nach Aufgabenstellung können Sie verschiedene Suchmethoden Primzahlen verwenden. Wenn Sie beispielsweise nach großen Mersenne-Primzahlen suchen, wird zunächst mit dem Sieb von Eratosthenes oder Atkin eine Liste von Primzahlen bis zu einer bestimmten Grenze festgelegt $$$10 ^ 8$ . Dann wird für jede Zahl p aus der Liste unter Verwendung des Luc-Lemer-Tests auf Einfachheit geprüft $$$M_p = 2 ^ p-1$ .

Um eine große Primzahl in kryptographische Zwecke zu erzeugen, wird eine Zufallszahl ausgewählt und überprüft von Miller-Rabin - Test oder das zuverlässigere Baillie-PSW. Nach dem Primzahlverteilungssatz ist für eine zufällig ausgewählte Zahl von 1 bis n die Wahrscheinlichkeit, Primzahl zu sein, ungefähr gleich $$${\ frac {1} {\ ln n}}$ . Um eine Primzahl von 1024 Bits zu finden, reicht es daher aus, etwa tausend Optionen zu sortieren.

PS-Quellen

Umsetzung aller beschriebenen Algorithmen auf der Go finden Sie unter GitHub .