- Einführung
- Primzahlen lassen sich einfach erklären, enthalten aber enorme Komplexität
- Sie werden in vielen Bereichen genutzt, etwa in mathematischen Konzepten, interessanter Visualisierung und Kryptografie
- Ich habe mich entschieden, die Erzeugung von Primzahlen per Programmierung anzugehen
- Herausforderung
- Primzahlen erzeugen, die in der RSA-Verschlüsselung eingesetzt werden können
- Für RSA-Schlüssel gilt derzeit eine passende Länge von 2048 Bit, daher werden zwei Primzahlen mit 1024 Bit benötigt
- Randbedingungen:
- Den Code von Grund auf selbst schreiben (ohne externe Abhängigkeiten)
- Nur die AMD Ryzen 7 CPU und 16 GB RAM des Notebooks verwenden
- Primzahlen in einer „angemessenen“ Zeit erzeugen
- Entscheidung für die Sprache Rust
- Erzeugung von 16-Bit-Primzahlen
- Pseudozufallsgenerator
/dev/urandom zur Erzeugung von Zufallszahlen nutzen
- Einfache Primzahlprüfung per Trial Division
- Im Schnitt gelingt die Erzeugung von 16-Bit-Primzahlen in ca. 40 ms
- Erzeugung von 64-Bit-Primzahlen
- Optimierten Trial-Division-Algorithmus implementiert
- Nur Zahlen in der Form 6k±1 prüfen
- Kleine Primzahlliste vorab erstellen, um leicht teilbare Zahlen früh zu filtern
- Nach der Optimierung etwa 6 Sekunden
- Für größere Zahlen liegt die Grenze für deterministische Verfahren
- Probabilistische Primzahltests
- Fermats kleiner Satz (Fermat's Little Theorem)
- Es gibt zusammengesetzte Zahlen, die die Bedingung ebenfalls erfüllen können (Pseudoprimes)
- Miller-Rabin Primality Test
- Eine probabilistische Primzahlprüfung, die Fermats Ansatz verbessert
- Eine zusammengesetzte Zahl ist für keine Basis immer ein Pseudoprime
- Die Fehlerwahrscheinlichkeit ist sehr gering, daher praktisch einsetzbar
- Erzeugung von 128-Bit-Primzahlen
- Mit dem Miller-Rabin-Test lässt sich schnell erzeugen (durchschnittlich 0,03 Sekunden)
- Durch den Grenzwert des u128-Typs ist eine Erweiterung auf 1024 Bit schwierig
- BigInt-Implementierung für 1024 Bit
- Mehrere Durchläufe mit schrittweisem Ausbau
- Versuch 1: Die Ziffern einer Zahl in einem Array speichern
- Versuch 2: Zahl als Binärzahl speichern
- Versuch 3: Zahl als Byte-Chunks speichern
- Versuch 4: Zahl als u64-Chunks speichern
- Versuch 5: Optimierung der Grundrechenalgorithmen
- Miller-Rabin-Prüfung und Gesamtlogik optimiert
- Parallelverarbeitung durch Multithreading genutzt
- Ergebnis
- 1024-Bit-Primzahlen können in ca. 40 ms erzeugt werden (8 ms ~ 800 ms)
- Durch Parallelverarbeitung liegt die durchschnittliche Laufzeit bei 0,04 Sekunden
Meinung von GN⁺
- Der iterative Verbesserungsprozess durch Versuch und Irrtum war beeindruckend
- Vom einfachen Einstieg aus wurden in jedem Schritt neue Ideen umgesetzt und Optimierungen vorgenommen
- Auch nach Fehlschlägen wurde nicht aufgegeben, stattdessen die Ursachen analysiert und Lösungen gesucht
- Bemerkenswert ist, dass der Autor trotz begrenzter mathematischer Vorkenntnisse recherchierte, um die notwendigen Konzepte zu verstehen
- Notwendige mathematische Grundlagen wie Fermats kleiner Satz oder der Miller-Rabin-Test wurden gelernt
- Auch schwierige Inhalte wurden so weit verstanden, dass sie implementierbar wurden
- Beeindruckend war die Umsetzung eines eigenen BigInt, um die Grenzen fester Ganzzahltypen zu überwinden
- Nicht nur bestehende Bibliotheken wurden genutzt, sondern deren interne Arbeitsweise verstanden und optimiert
- Der schrittweise Verbesserungsprozess mit unterschiedlichen Ideen war besonders auffällig
- Der Einsatz von Multithreading zur Parallelisierung, mit dem die Leistung deutlich verbessert wurde, war besonders interessant
- Die Struktur des Problems mit unabhängigen Berechnungen wurde gut erkannt und gezielt ausgenutzt
- Statt nur höhere Geschwindigkeit zu suchen, wurde ein effizienter, problembasierter Ansatz verfolgt
- Zwar kein kryptografisch sicheres Niveau, aber ein Projekt mit großem Wert als Lern- und Erkundungsprozess
- Nicht die sofortige praktische Nutzung, sondern die Neugier und der Innovationsgeist stehen im Vordergrund
- Die gewonnenen Erkenntnisse und Erfahrungen dürften dem Autor auf dem weiteren Weg stark helfen
1 Kommentare
Hacker News Kommentar
In diesem Zusammenhang verwenden einige Kryptowährungen im Rahmen ihrer Proof-of-Work-Funktion Dinge, die mit der Suche nach großen Primzahlen zusammenhängen. Vor etwa acht Jahren konnte man mit einer sehr schnellen Primzahlprüfung viel Geld verdienen. Der Autor war vorerst Entwickler und Betreiber der Mining-Software für Riecoin.
In diesem Beitrag wird die schnellste Optimierung für eine schnelle Primzahlprüfung, nämlich die Montgomery-Multiplikation, ausgelassen. Sie ist die Grundlage für eine schnelle, praktische Implementierung modularer Exponentiation.
Das von Niall Emmart veröffentlichte CGBN ist eine extrem schnelle GPU-bigint-Bibliothek. Es ist immer noch die schnellste batch modexp-Implementierung, die ich kenne.
Python enthält eine ziemlich gute modexp, die pow(x, y, m) → x^y % m berechnet. Damit lassen sich Fermat- oder Miller-Rabin-Primzahltests leicht implementieren.
Anfangs fand ich das Konzept der probabilistischen Primzahlprüfung seltsam und versuchte, einen deterministischen Algorithmus für riesige Zahlen zu finden. APR-CL und ECPP waren jedoch so mathematisch komplex, dass sie schwer verständlich sind. Mir wurde klar, dass man fast überall, einschließlich RSA, probabilistische Algorithmen verwendet.
Es ist trivial, Miller-Rabin für eine bestimmte obere Schranke deterministisch zu machen. Man muss nur Basen auswählen, von denen bewiesen ist, dass sie innerhalb eines gegebenen Bereichs alle Pseudoprimes ausschließen.
Eine einzeilige Inline-Assembly kann die Multiplikation großer Zahlen stark vereinfachen. Ich hätte mir gewünscht, dass C das Konzept der erweiterten Multiplikation hätte. Hardware-Unterstützung ist überall vorhanden.
Der Fermat-Test wäre ausreichend gewesen, weil der Algorithmus nicht funktioniert, wenn die Zahl tatsächlich nicht prim ist. Aber ich weiß nicht, ob man beweisen kann, dass es keine nicht-prime Werte für P/Q gibt, die eine erfolgreiche Verschlüsselung/Entschlüsselung von Nachrichten erlauben.
Es wäre interessant zu wissen, wie lange das Projekt gedauert hat. Der Autor implementierte Karatsuba, Toom-Cook, komplexes FFT, NTT und Schönhage–Strassen. Er empfiehlt Silvermans "A Friendly Introduction to Number Theory".
Ich kann nachvollziehen, wie schwierig es ist, hochrangige Erklärungen aus mathematischen Papieren in tatsächliche Berechnungen umzusetzen, wenn man eigenen Code zum Multiplizieren großer Zahlen schreibt. Im Teil über die Radix gibt es einen kleinen Fehler.
Statt Zahlen neu zu generieren, ist die letzte Optimierung, zwei hinzuzufügen, ein kleiner Sicherheitsverlust. Da Primzahlen nicht gleichmäßig verteilt sind, wird dadurch Richtung einer Primzahl verzerrt, die direkt hinter einem großen Primzahlenabstand liegt.
Bei der Beschreibung des kleinen Fermat-Theorems gibt es einen kleinen Fehler. Es wurde gesagt, dass a^(p-1) durch p teilbar sei, doch korrekt ist, dass a^(p-1) - 1 durch p teilbar sein muss. In den Modulares-Arithmetik-Begriffen wurde es korrekt beschrieben.