Der Solovay‑Strassen‑Test gehört zu den spannendsten probabilistischen Primzahltests der modernen Kryptographie. Dieser Text erklärt klar und verständlich, wie der Algorithmus funktioniert, warum das Jacobi‑Symbol dabei eine zentrale Rolle spielt und wie sich große Zahlen effizient auf Primalität prüfen lassen. Anschauliche Beispiele, präzise Herleitungen und ein Blick auf Fehlerwahrscheinlichkeit und Laufzeit machen das Thema greifbar – ideal für alle, die sich für Kryptographie, Zahlentheorie oder algorithmische Grundlagen interessieren. Ein fundierter, zugleich gut lesbarer Einstieg in einen Klassiker der Informatik.
Der Solovay-Strassen-Test
Florian Reuß
2. Juni 2020
1 Einleitung
Viele kryptographische Verfahren basieren auf den besonderen Eigenschaften von Primzahlen. Oft ist es beispielsweise für die Schlüsselerzeugung (vgl. RSA) nötig, große Primzahlen zu erzeugen. Eine systematische Generierung von Primzahlen ist allerdings weder effizient umsetzbar, noch kryptografisch sicher. Primzahlen müssen daher zufällig erzeugt werden: Hierzu werden solange Zufallszahlen generiert und auf ihre Primalität überprüft, bis eine Primzahl gefunden wurde. Unter anderem zu diesem Zwecke benötigt man Primzahltests.
Lange Zeit war es nur deterministisch und in zur Bitlänge der Eingabe exponentieller Laufzeit möglich, solche Tests durchzuführen. Der erste bekannte probabilistische Primzahltest ist der Fermat-Test, der bereits in zur Bitlänge der Eingabe kubischer Laufzeit eine Antwort zu geben vermochte, ob eine Zahl zusammengesetzt ist. Allerdings lässt der Test keine unmittelbaren Rückschlüsse darüber zu, ob die eingegebene Zahl wirklich prim ist (s. fermatsche Pseudoprimzahlen) und erkennt auch nicht alle zusammengesetzten Zahlen als solche (s. Carmichael-Zahlen). Mit dem im Jahre 1977 von R. Solovay und V. Strassen veröffentlichen Primzahltest konnte schließlich das Problem der Carmichael-Zahlen umgangen werden. Damit war es nunmehr möglich, Primzahlen effizient und zuverlässig zu erkennen und zu generieren.
Wir wollen in den folgenden Kapiteln einen kurzen Abriss über die Funktionsweise des Solovay-Strassen-Tests geben, ihn auf seine zahlentheoretische Grundlage zurückführen, seine Laufzeit analysieren und zuletzt die Fehlerwahrscheinlichkeit des Ergebnisses näher betrachten.
2 Funktionsweise und Ablauf
Der Ablauf des Solovay-Strassen-Tests wird durch folgenden Pseudocode beschrieben:
Abb. in Leseprobe nicht enthalten
a Also falls n eine Primzahl oder eine eulersche Pseudoprimzahl, siehe Theorem 3.1 und Definition 5.1
Der Test macht sich zunutze, dass die in Z. 9 berechnete Kongruenz für jedwede Primzahl p > 2 gilt und es darüber hinaus für jede zusammengesetzte Ganzzahl n > 2 ein a G { 1 , ...,n —
1 } gibt, sodass die Kongruenz nicht gilt. Auf dieser Basis werden Aussagen darüber möglich, ob die Eingabe sicher zusammengesetzt oder vermutlich prim ist. Wir werden zunächst den Zusammenhang zwischen Primalität und dieser spezifischen Kongruenz herstellen und dabei auch auf die Bedeutung des in Z. 9 verwendeten Symbols (a) eingehen.
3 Korrektheit
3.1 Quadratische Reste
Im Folgenden wollen wir zeigen, dass der Algorithmus 1 alle Primzahlen p> 2 korrekt als solche identifiziert, also dass für alle Primzahlen p> 2 solovayStrassen (p) = falsch gilt. Gemäß der Definition des Algorithmus ist hierfür zu zeigen, dass für jede Primzahl p> 2 und jedes a E { 1 , ...,p — 1 } gilt: (a) = a ( p - 1) / [2] (mod p).
Definition 3.1 (Quadratischer Rest) . Eine Ganzzahl a heißt quadratischer Rest modulo m für eine Ganzzahl m > 2, wenn ggT (a, m) = 1 und wenn es eine Ganzzahl x gibt, sodass a = x [2] (mod m). Wenn ggT (a, m)=1und a kein quadratischer Rest modulo m ist, so heißt a quadratischer Nichtrest modulo m. [5, S. 85]
Definition 3.2 (Legendre-Symbol) . Für eine ungerade Primzahl p und eine Ganzzahl a ist
Abb. in Leseprobe nicht enthalten
das Legendre-Symbol von a und n.
Lemma 3.1 (Euler’s Kriterium) . Sei p eine ungerade Primzahl und a Ganzzahl mit ggT (p, a)= 1 , dann gilt
Abb. in Leseprobe nicht enthalten
Beweis. siehe [6, S. 269]
Aus Theorem 3.1 folgt bereits die Korrektheit des Algorithmus 1.
3.2 Das Jacobi-Symbol
Der Solovay-Strassen-Test akzeptiert allerdings auch zusammengesetzte Zahlen n> 2 als Eingaben. Bislang können wir das Legendre-Symbol in Z. 10 des Algorithmus 1 aber lediglich für Primzahlen berechnen. Wir benötigen also eine Verallgemeinerung des Legendre-Symbols auf alle ungeraden Zahlen n> 2:
Definition 3.3 (Jacobi-Symbol) . Sei n> 2 eine ungerade Ganzzahl mit der Primfaktorzerlegung n = p 1 ...p r . Für eine Ganzzahl a heißt (a) = p^ (r^ Jacobi-Symbol von a und n. [5, S. 87]
Um uns mit der Definition vertraut zu machen, werden wir einige Eigenschaften des Jacobi- Symbols betrachten. Falls n eine ungerade Primzahl ist, dann ist das Jacobi-Symbol (a) dasselbe wie das Legendre-Symbol. Daher können wir ohne Einschränkungen für Beide dieselbe Notationsform verwenden. Falls ggT (a, n) > 1, dann besitzen a und n mindestens einen gemeinsamen Primfaktor p i [vgl. 13, S. 19-20]. Für diesen ist dann (pai) = 0 und daher ist in diesem Fall auch (a) = 0. So ist zum Beispiel (291) = 0, obwohl 9 ein quadratischer Rest modulo 21 ist. Interessanter ist der Fall, dass ggT (a,n) = 1. Selbst in diesem Fall lässt (a) keine Rückschlüsse darüber zu, ob a ein quadratischer Rest modulo n ist oder nicht! Beispielsweise ist (125) = (!) * (!) = (— 1)(— 1) = 1, obwohl 2 ein quadratischer Nichtrest modulo 15 ist. Wir halten also fest, dass der Wert des Jacobi-Symbols keine unmittelbaren Aussagen über die Eigenschaft, quadratischer Rest zu sein, zulässt.
4 Zeitkomplexität
Im Folgenden wollen wir eine obere Schranke für die Worst-Case-Laufzeit des Algorithmus 1 identifizieren. Da Algorithmus 1 weder Schleifen noch Rekursion aufweist, ist er terminierend, solange alle von ihm aufgerufenen Unterprogramme terminierend sind. Dass dies der Fall ist, werden wir ebenfalls in diesem Abschnitt zeigen. Die Gesamtlaufzeit des sequentiellen Algorithmus ergibt sich schließlich als Summe der Laufzeiten der einzelnen Berechnungsschritte.
In Z. 2 wird zunächst ein Paritätstest durchgeführt. Der Aufwand für diese Operation ist konstant und damit vernachlässigbar, da lediglich das niederwertigste Bit der Zahl betrachtet werden muss. Der Aufwand für den in Z. 5 benötigten Zufallsgenerator ist ebenfalls vernachlässigbar. Wesentliche Aufwände entstehen lediglich für die Berechnung des größten gemeinsamen Teilers in Z. 6, für die modulare Potenzierung in Z. 9 sowie die Berechnung des Jacobi-Symbols in Z. 10.
Für eine positive Ganzzahl n sei || n | | = |"log 2 (n +1) 1 die Anzahl der Bits in der Binärdarstellung von n, wobei | |0 1 | = 1. Dann gilt für die elementaren Operationen bei beliebigen positiven Ganzzahlen a, b, n nach [5]:
• Um a ± b zu berechnen, werden O(||a | | + ||b |) Schritte benötigt.
• Um a * b zu berechnen, werden O(||a|| * ||b ||) Schritte benötigt.
• Um a mod n zu berechnen, werden O(||a|| * ||n | |) Schritte benötigt.
• Um a * b mod n zu berechnen, werden O(||n ||2) Schritte benötigt.
• Um ggT(a,b) zu berechnen, werden (mit dem euklidschen Algorithmus) O(||a||*||b | |) Schritte benötigt.
4.1 (Schnelle) modulare Potenzierung
Die modulare Potenzierung ist ein spannendes und für den Solovay-Strassen-Test wesentliches Beispiel für eine Elementaroperation auf positiven Ganzzahlen. Angenommen, wir wöllten die Zahl 2 [10987654321] mod 101 berechnen. Es läge auf der Hand, die 2 einfach 10987654320-mal mit sich selbst zu multiplizieren und in jedem Schritt den Rest bei der Division durch 101 zu bestimmen. Diese Methode ist jedoch hochgradig ineffizient. Tatsächlich würde bei dieser Methode die Anzahl an benötigten Schritten exponentiell zur Bitlänge der Eingabe steigen. Wir benötigen also für den Solovay-Strassen-Test, der ja in jeder Runde modulare Potenzen berechnen muss, ein effizienteres Verfahren.
Wir werden hierfür das Verfahren der binären Exponentiation — auch Square-And-Multiply- Methode genannt — vorstellen. Die Grundlage für die Methode bildet das folgende Korollar:
Lemma 4.1. Für beliebige positive Ganzzahlen a, n, m gilt
Abb. in Leseprobe nicht enthalten
Beweis. Für alle positiven Ganzzahlen n gilt zunächst n = 2 * [ n J + (n mod 2). Es gilt:
Abb. in Leseprobe nicht enthalten
Abb. in Leseprobe nicht enthalten
Aus Theorem 4.1 sowie dem Fakt, dass a [0] =1 für jede beliebige Ganzzahl a, lässt sich der folgende rekursive Algorithmus ableiten:
Lemma 4.2 (Korrektheit des Algorithmus 2) . Für beliebige positive Ganzzahlen a, n, m gilt expM od (a, n, m)= a n mod m.
Beweis. Für n =0gilt expM od (a, 0 ,m)=1= a [0] mod m. Angenommen, es gelte expMod (a,n',m ) = a n mod m für eine beliebige positive Ganzzahl n. Dann ist
Abb. in Leseprobe nicht enthalten
Analog dazu ist expMod (a, 2 n + 1 ,m ) = a n mod m. Aufgrund des Induktionsprinzips gilt expMod (a,n,m) = a n mod m. □
Lemma 4.3. Um a n mod m zu berechnen werden O(||n || * ||m | |[2]) Schritte benötigt.
Beweis. Sei t(||n| |) die durch den Algorithmus benötigte Zeit bei einer Eingabe der Länge || n|| und c(||n| |) der Aufwand zum Zerlegen der Eingabe und zur Kombination der Lösung aus den Teillösungen. Dann lässt sich für den Algorithmus folgende Rekursionsgleichung aufstellen:
Abb. in Leseprobe nicht enthalten
In jedem Rekursionsschritt wird genau ein Rekursionsaufruf getätigt, wobei die Zahl n bei jedem Aufruf halbiert wird, was einem Bit Shift um eine Stelle entspricht. Zum Zerlegen der Eingabe muss diese halbiert werden, also lediglich die Zahl um ein Bit geshiftet werden. Dieser Aufwand ist als konstant vernachlässigbar. Bei der Kombination der Lösung aus den Teillösungen fällt hingegen höchstens, nämlich dann, wenn der Algorithmus in Z. 6 gelangt, folgender Aufwand an:
1. Überprüfung, ob n ungerade oder 0 ist: Konstante Zeit, da lediglich das niederwertigste Bit überprüft werden muss.
2. Quadrierung mit Modul m: O(Wm W 2 )
3. Multiplikation mit Modul m: O(||m | |2)
Also ist Abb. in Leseprobe nicht enthalten und damit gilt für die Gesamtlaufzeit des Algorithmus Abb. in Leseprobe nicht enthalten
Abb. in Leseprobe nicht enthalten
4.2 Berechnung des Jacobi-Symbols
In diesem Abschnitt wollen wir uns der Frage zuwenden, wie das Jacobi-Symbol (^) für eine ungerade Ganzzahl n> 2 und eine Ganzzahl a möglichst effizient berechnet werden kann. Der naive Ansatz wäre es hier, die Primfaktorzerlegung von n zu bestimmen, die einzelnen Legendre- Symbole für die Primfaktoren zu berechnen und schließlich miteinander zu multiplizieren. Da für die Faktorisierung einer Zahl aber kein effizientes Verfahren zur Verfügung steht, ist dieser Ansatz nicht praktikabel. Der Solovay-Strassen-Test macht sich allerdings zunutze, dass sich das Jacobi-Symbol über bestimmte Rechengesetze effizient berechnen lässt. Wir werden diese im Folgenden kurz betrachten:
Lemma 4.4 (Grundlegende Rechengesetze für das Jacobi-Symbol) . Für jede ungerade Ganzzahl n> 2 gilt:
Abb. in Leseprobe nicht enthalten
3. Gilt trivialerweise, da 1 für jede Primzahl p> 2 ein quadratischer Rest modulo p ist.
4. Gilt trivialerweise, da 0 ein Vielfaches jeder Primzahl p> 2 ist.
Um weitere Zusammenhänge zwischen Jacobi-Symbolen zu finden, betrachten wir zunächst einige ausgewählte Werten für n, welche in Abb. 1 aufgeführt sind.
Abb. in Leseprobe nicht enthalten
Abbildung 1: Einige Werte für das Jacobi-Symbol (^). Statt 1 schreiben wir + und statt — 1 schreiben wir -. Entnommen aus [5, S. 89]
Bei näherer Betrachtung werden bestimmte Muster erkennbar: So wechseln sich in der Spalte für a = 2 immer und ++ ab, es scheint also (2) = 1 zu sein, wenn n = 1 oder 7 (mod 8)
und (2) = — 1 zu sein, wenn n = 3 oder 5 (mod 8).
Beim Vergleich der Zeile n =5mit der Spalte a = 5 fällt auf, dass diese (zumindest im dargestellten Tabellenbereich) übereinstimmen. Ähnliche Beziehungen lassen sich zwischen n = 13 und a =13, n =21und a = 21 oder n =29und a = 29 beobachten. Für andere Paare aus Zeile und Spalte ist die Situation ein wenig vertrackter. So haben die Zeile n =11und die Spalte a =11 zwar nicht dieselben Einträge, aber bei einem eingehenden Vergleich fällt auf, dass sich gleiche und entgegengesetzte Werte abwechseln: (11) = — (11) , (11) = (151) , (171) = — (171) etc. Ähnliche Beziehungen lassen sich für die Zeilen/Spalten 3, 19 und 27 beobachten. Das Gesetz, welches den Zusammenhang zwischen 1) und n festhält, ist einer der Hauptsätze der Zahlentheorie: das na quadratische Reziprozitätsgesetz.
Theorem 4.5 (Quadratisches Reziprozitätsgesetz) . Sind n und m zwei Ganzzahlen mit n, m > 2 , so gilt:
Abb. in Leseprobe nicht enthalten
Beweis. Den ersten Beweis stellte Gauß 1801 in seinen Disquisitiones Arithmeticae auf; ausführ- liehe Beweise finden sich aber unter anderem auch in [5, S. 137-142] und [12, S. 75-89]. □
Aus den vorgestellten Rechengesetzen kann nun der folgende rekursive Algorithmus abgeleitet
werden:
Abb. in Leseprobe nicht enthalten
a Im Kontext des Solovay-Strassen-Algorithmus wird das Jacobi-Symbol stets nur für positive Werte berechnet
Lemma 4.7 (Korrektheit des Algorithmus 3) . Für jede positive Ganzzahl a und jede ungerade
Ganzzahl n> 2 gilt jacobi (a,n) = (t)
Beweis. Falls der Algorithmus terminierend ist (also nicht in eine Endlosrekursion gerät), dann liefert er auch das korrekte Ergebnis zurück, da er eine unmittelbare rekursive Implementierung der vorgestellten Rechengesetze darstellt. Der Algorithmus ist aufgrund von Theorem 4.8 terminierend. □
Lemma 4.8 (Zeitkomplexität der Berechnung des Jacobi-Symbols) . Um (^) zu berechnen, werden O(||a | |[2] * ||n | |) Schritte benötigt.
Beweis. Um Aussagen über die Laufzeit von Algorithmus 3 treffen zu können, müssen wir zunächst analysieren, wie viele Rekursionsschritte er benötigt. Hierbei ist zunächst festzustellen, dass die Terminierung des Algorithmus allein vom Wert von a abhängig ist. Sobald a =0oder a = 1 befinden wir uns im letzten Rekursionsaufruf. Sei a t der Wert des Parameters a im t -ten Rekursionsaufruf. Wir wollen zeigen, dass für alle a,n> 2 gilt a t +2 < at, sprich dass der Wert von a sich nach zwei Rekursionsaufrufen mindestens halbiert hat. Bei jedem Aufruf des Algorithmus wird genau eine der bedingten Anweisungen ausgeführt: Falls Z. 5 ausgeführt wird, so gilt bereits a t +1 = a mod n < a, da a > n. Falls Z. 9 bzw. Z. 11 ausgeführt werden, gilt direkt a t +1 = L a J. Interessant sind die Fälle in Z. 13 und Z. 15.
Falls im t -ten Rekursionsschritt Z. 13 oder 15 ausgeführt wird und im folgenden Schritt eine der anderen Zeilen, so hat sich der Wert für a mindestens halbiert, weil n mod a<a. Falls sowohl im t -ten als auch t + 1-ten Rekursionsschritt Z. 13 oder 15 ausgeführt wird, dann ist a t +2 < a t mod (n mod a t), da der Wert des Parameters n im t -ten Rekursionsaufruf nur noch höchstens so groß ist wie der initiale Wert des Parameters. Es bleibt also zu zeigen, dass a t mod (n mod a t ) < at für ein beliebige a t,n > 2.
Wir beginnen mit einer Fallunterscheidung:
(1) Falls a t > 2n ist insbesondere at > n. Weiterhin gilt n mod a t = n und damit a t mod (n mod a t ) = a t mod n < n < at.
(2) Falls n < a t < 2n gilt n mod a t = n und a t mod (n mod a t ) = a t mod n = a t — L at J * n. Da 1 n < a t < 2 n ist insbesondere L tt J = 1 und damit a t — L at J * n = a t — n.Da n > at ist at — n < at — at = at.
(3) Falls a t = n, so ist a t mod (n mod a t ) = 0 und 0 < at, da a t > 2.
(4) Falls a t <n gilt n mod a t <a t. Der übrige Beweis verläuft analog zu Fall (2).
Der Wert von a wird also alle zwei Aufrufe mindestens halbiert und wird demnach spätestens nach 2 * ||a| | Rekursionsschritten 0 oder 1 erreichen. Die einzigen nennenswerten Aufwände, die in einem Rekursionsschritt potentiell anfallen können, sind die modulo-Operationen in Z.5, Z. 13 oder Z. 15. Für diese werden jeweils O(||n|| * ||a ||) Schritte benötigt. Alle anderen Berechnungen sind modulo-Divisionen durch Zweierpotenzen und daher unter Voraussetzung einer Binärdarstellung in konstanter Zeit zu berechnen. Damit liegt die Gesamtlaufzeit des Algorithmus 3 in O(||a ||[2] *\\n \\). □
Wenngleich die Worst-Case-Komplexität aller bislang zur Berechnung des Jacobi-Symbols existierenden Algorithmen O(||n | |3) beträgt, gibt es durchaus Algorithmen mit einer wesentlich besseren Average-Case-Komplexität als Algorithmus 3. Ein recht aktuelles Beispiel für einen solchen Algorithmus findet sich in [8].
Die Gesamtlaufzeit des Algorithmus 1 ergibt sich abschließend als Summe der einzelnen Teillaufzeiten und liegt somit in O(||n| |3). Damit vermag der Algorithmus 1 in polynomieller Zeit probabilistisch zu entscheiden, ob eine Ganzzahl n> 2 zusammengesetzt ist.
(5) Fehlerwahrscheinlichkeit
In Abschnitt 3 haben wir uns der Frage zugewendet, ob der Algorithmus alle Primzahlen korrekt als solche identifiziert und gezeigt, dass dies der Fall ist. Im Folgenden wollen wir uns mit der Frage beschäftigen, ob der Algorithmus auch alle zusammengesetzten Zahlen stets korrekt als solche ausweist, also ob für alle zusammengesetzten Zahlen solovayStrassen (n) = wahr gilt. Tatsächlich ist dies nicht der Fall, ansonsten hätte man schon damals im Jahre 1977 eine deterministische Variante des Tests bauen können, um zu beweisen, dass PRIMES e P 2. Es gibt also zusammengesetzte Zahlen n, welche die im eulerschen Kriterium postulierte Kongruenz Abb. in Leseprobe nicht enthalten (mod n ) erfüllen. Diese Zahlen bezeichnet man als eulersche Pseudoprimzahlen.
5.1 Eulersche Pseudoprimzahlen
Definition 5.1 (Eulersche Pseudoprimzahl) . Für eine Ganzzahl a heißt eine ungerade zusammengesetzte Ganzzahl n mit Abb. in Leseprobe nicht enthalten (mod n ) eulersche Pseudoprimzahl zur Basis a. [9, S. 97]
Salopp gesagt ist eine eulersche Pseudoprimzahl also eine zusammengesetzte Zahl, die gewissermaßen nur vortäuscht, eine Primzahl zu sein. Ein Beispiel für eine solche eulersche Pseudoprimzahl zur Basis 7 ist die 25. Es gilt ggT (7, 25) = 1 und (25) = (7)(7) = 1 = 7 [12] mod 25. Es gibt also mindestens eine eulersche Pseudopimzahl und damit mindestens eine zusammengesetzte ungerade Ganzzahl, für die der Algorithmus nicht in jedem Fall falsch zurückgibt. Tatsächlich gibt es zu jeder Basis a > 2 sogar unendlich viele eulersche Pseudoprimzahlen. Ein Beweis hierfür ist in [7] nachzulesen. Der Algorithmus erkennt also nicht alle zusammengesetzten Zahlen als solche. Mindestens dann wenn eine Eulersche Pseudoprimzahl zur Basis a eingegeben wird und der Algorithmus randomisiert die Zahl a auswählt, gibt er ein unzutreffendes Ergebnis zurück.
5.2 RP-Algorithmen
Doch wie groß ist die Wahrscheinlichkeit dafür, dass der Algorithmus ein unzutreffendes Ergebnis (also falsch, obwohl n gar keine Primzahl war) zurückliefert? Dazu werden wir zunächst betrachten, in welchen Fällen der Algorithmus zusammengesetzte Zahlen korrekt als solche identifiziert (also wahr zurückgibt). Aus der Kontraposition von Theorem 3.1 wissen wir, dass dies der Fall ist, wenn der Algorithmus für eine eingegebene zusammengesetzte Ganzzahl n> 2 ein a e { 1 , ...,n — 1 } (zufällig) auswählt, sodass (n) ^ a ( n - 1) / [2] (mod n).
Definition 5.2 (Euler-Zeuge) . Sei n eine ungerade zusammengesetzte positive Ganzzahl. Eine Zahl Abb. in Leseprobe nicht enthalten wird Euler-Zeuge für n genannt. [5, S. 93]
Beispiel 5.1. Betrachten wir die zusammengesetzte Ganzzahl n = 325. Für a = 15 gilt ggT (15 , 325) = 5 und daher (325) = 0. Die 15 ist also Euler-Zeuge für 325. Für a = 2 gilt 2 [162] mod 325 = 129, also ist die 2 ebenfalls Euler-Zeuge für 325. Für a =7gilt 7 [162] mod 325 = 324 und (375) = — 1; also ist die 7 kein Euler-Zeuge für 325 und die 325 ist eine eulersche Pseudoprimzahl zur Basis 7. Der Algorithmus würde hier also in dem Fall, dass er (zufällig) a =7 gewählt hat, ein unzutreffendes Ergebnis ausgeben.
Um mit Sicherheit nachzuweisen, dass eine Zahl n zusammengesetzt ist, genügt es also, einen Euler-Zeugen für n zu finden2. Ein Euler-Zeuge „bezeugt“ also gewissermaßen die Zusammengesetztheit und damit die „Nichtprimalität“ einer Ganzzahl. Aber lässt sich zu jeder ungeraden zusammengesetzten positiven Ganzzahl auch mindestens ein Euler-Zeuge finden?
Theorem 5.1. Für jede ungerade zusammengesetzte positive Ganzzahl gibt es mindestens einen Euler-Zeugen a.
Beweis. Wir betrachten zwei Fälle: (1) In der eindeutigen Primfaktorzerlegung von n tritt mindestens ein Primfaktor mehrfach auf und (2) n ist quadratfrei3
(1) Angenommen, in der eindeutigen Primfaktorzerlegung von n kommt (mindestens) ein Primfaktor p mehrfach vor. Dann ist n = p km für ein k > 2 und eine positive Ganzzahl m. Da p kein Faktor in der Primfaktorzerlegung von m ist, gilt ggT (p, m)=1. Nach dem chinesischen Restsatz4 hat die simultane Kongruenz
Abb. in Leseprobe nicht enthalten
eine eindeutige Lösung modulo n. a ist nicht durch p [2] und damit insbesondere nicht durch p teilbar, und ggT (a, m)=1und daher auch ggT (a, n)=1.
Angenommen, es gelte (n) = a ( n - 1) / [2] (mod n). Es gilt (n) = ± 1, da a zu jedem Primfaktor von n teilerfremd ist und durch Quadrierung erhalten wir a ( n - 1) = 1 (mod n). Da p [2] ein Teiler von n ist, lässt sich diese Kongruenz auf a ( n - 1) = 1 (mod p [2]) reduzieren. Da weiterhin a = 1 + p (mod p [2]) ist, erhalten wir (1 + p ) ( n - 1) = 1 (mod p [2]). Durch Anwendung des binomischen Lehrsatzes erhalten wir 1 + (n — 1) p = 1 (mod p [2]). Zieht man die 1 auf beiden Seiten der Kongruenz ab, so erhält man (n — 1) p = 0 (mod p [2]), beziehungsweise n — 1 = 0 (mod p).Da n ein Vielfaches von p ist, stellt dies einen Widerspruch dar und a muss dementsprechend Euler-Zeuge von n sein.
(2) Angenommen, n wäre quadratfrei und n = p 1 p 2 ...p r mit n> 2 (n ist per Voraussetzung nicht prim!) die Primfaktorzerlegung von n und die einzelnen p i ’s ungerade Primzahlen. Nach [5, S. 86] gibt es für einen ungeraden Primzahlmoduln genau p — [1] quadratische Nichtreste. Es muss also mindestens eine Ganzzahl b geben, sodass (¡ -) = — 1. Nach dem chinesischen Restsatz hat die simultane Kongruenz
a — b (mod p 1) , a — 1 (mod p 2 ...p r)
eine eindeutige Lösung modulo n, da p 1 p 2 ...p r Primfaktorzerlegung von n ist und damit alle p i paarweise teilerfremd sind. Da die Zahl b quadratischer Nichtrest von p 1 und damit per Definition ggT (b, p 1)=1ist, gilt auch ggT (a, p 1)=1. Weiterhin ist die Zahl a teilerfremd zu p 2 ...p r , also ggT (a, n) = 1. Für alle p i mit i > 1 gilt (i^ = (p l i) = 1 aufgrund der Berechnungsvorschrift für das Legendre-Symbol. Nach Definition 3.3 gilt somit für das Jacobi-Symbol Abb. in Leseprobe nicht enthalten
Angenommen, (J) * a ( n - 1) / 2 mod n = 1, also a (" - 1) / 2 — — 1 (mod n). Da p 2 ein Teiler von n ist, lässt sich diese Kongruenz auf a ( J - 1) / 2 — — 1 (mod p 2 ) reduzieren. Da weiterhin a — 1 (mod p 2 ) ist, erhalten wir 1 — — 1 (mod p 2). Da n ungerade ist und p 2 demnach größer als 2 sein muss, stellt dies einen Widerspruch dar und a muss dementsprechend Euler-Zeuge von n sein.
Wählt der Algorithmus für eine eingegebene zusammengesetzte ungerade Ganzzahl n also ein a e { 1 ,...,n — 1 }, so ist die Wahrscheinlichkeit, dass (J) — a ( J - 1) / 2 (mod n) gilt und der Algorithmus somit ein ”falsches” Ergebnis liefert < 1. Doch wie groß ist diese Fehlerwahrscheinlichkeit genau? Für wie viele Zahlen a e { 1 , ...,n — 1 } gilt die Kongruenz (J) — a ( J - 1) / 2 (mod n), obwohl n eine zusammengesetzte Zahl ist?
Korollar 5.1.1. Sei n> 2 eine beliebige, aber feste ungerade zusammengesetzte Ganzzahl, dann
Abb. in Leseprobe nicht enthalten
Beweis. Gemäß Definition 3.3 ist (J) = ± 1 falls ggT (a, n) = 1 und (J) = 0 falls ggT (a, n) > 1. Sei
Abb. in Leseprobe nicht enthalten
C = { 1 < a < n — 1 | ggT (a, n) > 1 }
Die Mengen A, B und C sind disjunkt mit A U B U C = { 1 , ...,n — 1 }. Die Menge A ist nichtleer, da die 1 in der Menge enthalten ist. Die Menge C ist nichtleer, da n zusammengesetzt ist und dementsprechend mindestens einen Teiler besitzen muss. Gemäß Theorem 5.1 ist die Menge B ebenfalls nichtleer. Wir wollen zeigen, dass |A | < J - 1 .
Sei b 0 e B beliebig aber fest. Wir werden zeigen, dass die Menge Ab 0 = { (ab 0) mod n | a e A } eine Teilmenge von B ist. Es gilt
(ab 0)(J- 1) / 2 - a (J- 1) / 2 b (0 J- 1) / 2 -
Da alle Zahlen in A und B teilerfremd zu n sind und damit keine gemeinsamen Primfaktoren mit n haben, hat auch die Zahl (ab 0) mod n keine gemeinsamen Primfaktoren mit n. Es gilt demnach ggT ((ab 0) mod n, n)=1und (ab 0) mod n muss daher in genau einer der disjunkten Mengen A oder B liegen.
Angenommen, (ab 0) mod n e A. Dann müsste gelten (ab 0 ) ( n - 1) / [2] = ab^) (mod n). Gemäß Theorem 4.4 gilt (n) = (n)(b 0) und da a e A gilt weiterhin a ( n - 1) / [2] = (n) (mod n). Also muss für (ab 0) mod n gelten, dass (n) = (n) b 0 n - 1) / [2] (mod n). Da ggT (a,n) = 1 ist (n ) = ± 1, also können wir (n ) auf beiden Seiten der Kongruenz streichen und erhalten (n ) = b 0 n - 1) / 2 (mod n). Dies steht aber im Widerspruch zu b 0 e B. (ab 0) mod n kann also nicht in A gelegen haben. Vielmehr gilt für alle a e A, dass (ab 0) mod n e B, folglich Ab 0 C B.
Wir werden nun zeigen, dass |A | = Ab 0 1. Die Funktion f b 0 : A ^ Ab 0 , f (a) = ab 0 mod n ist injektiv, denn wenn ab 0 = a'b 0 (mod n) für a, a[1] e A, so lässt sich b 0 aus der Kongruenz streichen und man erhält a = a! (mod n) und insbesondere a = a!, da alle Elemente in A zwischen 0 und n liegen. f b 0 ist weiterhin surjektiv aufgrund der Definition der Menge Ab 0, also gilt |A | = | Ab 0 |.
Da Ab 0 C B gilt |A | = Ab 0 1 < \B \. Daher gilt weiterhin
n - 1 = | A| + \ B\ + C| > | A| + | A| + 1 > 2 | A| ,
also n - 1 > 2 | A |. Daraus folgt |A | < n - [1]. □
Bei Eingabe einer zusammengesetzten ungeraden Ganzzahl n in den Solovay-Strassen-Test, gibt es also weniger als n - [1] potentiell wählbare Zufallswerte, für die der Test zu einem unzutreffenden Ergebnis gelangt. Wir nennen diese Werte entsprechend falsche Euler-Zeugen. Aufgrund seiner Eigenschaften lässt sich der Algorithmus in eine spezifische Klasse von Algorithmen einordnen:
Definition 5.3 (Randomized Polynomial Time) . Eine Sprache L liegt genau dann in der Komplexitätsklasse RP, wenn ein polynomiell zeitbeschränkter probabilistischer Algorithmus A 6 sowie eine Wahrscheinlichkeit 0 <p < 1 existieren, für die gilt:
• n e L ^ Prob [ A (n) = wahr] > p
• ne L ^ Prob [ A (n) = falsch] = 1
A nennen wir dann RP -Algorithmus oder Monte-Carlo-Algorithmus für L mit einseitigem Fehler (1 - p). [13, S. 57] und [2, S. 115]
Lemma 5.2. Sei COMPOSITES das Entscheidungsproblem {n e Z > 2 | n ist zusammengesetzt }. Algorithmus 1 ist ein RP-Algorithmus für COMPOSITES mit einseitigem Fehler 2 .
Beweis. Algorithmus 1 ist probabilistisch und polynomiell zeitbeschränkt (siehe Abschnitt 4). Falls n > 2 eine zusammengesetzte Zahl ist, dann gibt es gemäß Korollar 5.1.1 weniger als n - [1] falsche Euler-Zeugen für n. Damit ist Prob [ solovayStrassen (n) = wahr] > 1. Falls n > 2 keine zusammengesetzte Zahl ist, dann ist sie prim und Prob [ solovayStrassen (n) = falsch] = 1 wegen Theorem 3.1. □
Damit ist ebenfalls bewiesen, dass COMPOSITES eRP und PRIMES e co -RP, was zur Zeit der ersten Veröffentlichung des Algorithmus (1977) eine bahnbrechende und äußerst nützliche Entdeckung gewesen ist: Primzahltests waren nicht länger ein Ding der Unmöglichkeit.
5.3 Fortgesetzte/iterierte Fehlerwahrscheinlichkeit
Vielmehr verfügen wir nun über einen Algorithmus, der in kubischer Laufzeit probabilistisch testen kann, ob eine Zahl zusammengesetzt ist und dessen Ergebnis mit mindestens 50% Wahrscheinlichkeit zutrifft. Die erreichte Fehlerwahrscheinlichkeit erscheint vielleicht zunächst nicht wirklich beeindruckend, doch die wahre Stärke von RP -Algorithmen offenbart sich erst in der Iteration:
Sei A ein RP -Algorithmus für ein Entscheidungsproblem L und A k mit k> 0 die k -fache stochastisch unabhängige Iteration von A, wobei A k genau dann wahr zurückgibt, wenn der Rückgabewert von A in jeder Iteration ebenfalls wahr war. Sei weiterhin P k = P rob [ A k (n)= falsch A n E L ] die Fehlerwahrscheinlichkeit von A k. Dann gilt P k < (P 1 ) k, die Fehlerwahrscheinlichkeit des Algorithmus lässt sich also durch Iteration immer weiter senken.
Wir haben soeben die Wahrscheinlichkeit abgeschätzt, dass der Solovay-Strassen-Test für eine gegebene zusammengesetzte Zahl n innerhalb von k Iterationen keinen Euler-Zeugen für n findet. Vielmehr interessiert uns aber die Wahrscheinlichkeit, dass eine Zahl zusammengesetzt ist, wenn der Solovay-Strassen-Test in k Iterationen keinen Euler-Zeugen für die Zahl ausmachen kann. Dies ist ein Verwechslung der bedingten Wahrscheinlichkeiten, die mit dem Satz von Bayes korrigiert werden kann. Hierfür muss unter anderem die Verteilung der Primzahlen (s. Primzahlsatz) berücksichtigt werden. Wendet man den Satz von Bayes korrekt an, so erhält man P k < ln n * (P 1 ) k falls 2 k > ln n. Eine ausführliche Darlegung der Rechenschritte findet sich in [3, S. 8-10].
In Bezug auf den Solovay-Strassen-Test bedeutet dies: Um mit mindestens 99 , 9% Wahrscheinlichkeit sicher sein zu können, dass eine gegebene 2048 Bit lange Zahl eine Primzahl ist, muss der Test 21 Mal iteriert werden.
5.4 Bezug zu Miller-Rabin
Wir konnten bislang nur zeigen, dass die Fehlerwahrscheinlichkeit P 1 für den Solovay-Strassen- Test höchstens 50% beträgt, wir wissen jedoch nicht, wie weit unter dieser Grenze sie tatsächlich liegt. [3] legt nahe, dass die 50% beim Solovay-Strassen-Test eine relativ scharfe Grenze ist, die meist nicht deutlich unterschritten wird. Es gibt jedoch probabilistische Primzahltests mit einer geringeren Fehlerwahrscheinlichkeit; ein Beispiel für einen solchen Test ist der Miller-Rabin-Test.
Die Grundidee des Verfahrens basiert ebenfalls auf dem kleinen fermatschen Satz und dem damit verbundenen Primzahltest (Fermat-Test), der Miller-Rabin-Test überprüft die Eingabe jedoch nicht auf das eulersche Kriterium hin. Er prüft vielmehr für ein eingegebene Ganzzahl n > 2 und ein randomisiert gewähltes Abb. in Leseprobe nicht enthalten. Dieses Kriterium kann nur durch Primzahlen oder sogenannte starke Pseudoprimzahlen erfüllt werden, wobei jede starke Pseudoprimzahl zugleich auch eulersche Pseudoprimzahl ist. Allerdings ist die Anzahl falscher Zeugen für eine starke Pseudoprimzahl stets < p (n )/ 4. Daraus ergibt sich, dass die einseitige Fehlerwahrscheinlichkeit für den Miller-Rabin-Test höchstens bei 25 % liegt. Diese Schranke wird nur für Extremfälle erreicht, durchschnittlich liegt sie sogar unter Abb. in Leseprobe nicht enthalten.
Darüber hinaus hat der Miller-Rabin-Test in der Praxis auch ein besseres Laufzeitverhalten als der Solovay-Strassen-Test: Obwohl seine Rechenzeit ebenfalls in O (|| n | |3) liegt, greift das Verfahren auf einfachere Operationen zurück. So benötigen zwar beide Verfahren modulare Potenzierung, der Miller-Rabin-Test kommt jedoch statt der Berechnung des Jacobi-Symbols in kubischer Laufzeit mit höchstens || n | | Quadrierungen aus7. Der Miller-Rabin-Test ist daher der in der Praxis bevorzugt eingesetzte probabilistische Primzahltest8.
Trotz alledem hat der Solovay-Strassen-Test in der Welt der Kryptographie große historische Bedeutung; stellte er doch den Durchbruch darin dar, die praktische Umsetzbarkeit des RSA- Kryptosystems zu zeigen.
Literatur
[1] Manindra Agrawal, Neeraj Kayal und Nitin Saxena. „ PRIMES is in P“. In: Annals of Mathematics (2004).
[2] Sanjeev Arora. Computational complexity : a modern approach. Cambridge New York: Cambridge University Press, 2009. isbn: 978-0-521-42426-4.
[3] Keith Conrad. „The Solovay-Strassen-Test“. url: https : / / kconrad . math . uconn . edu/ blurbs/ugradnumthy/solovaystrassen.pdf.
[4] Ivan Damgard, Peter Landrock und Carl Pomerance. „Average Case Error Estimates for the Strong Probable Prime Test“. In: Mathematics of Computation 61.203 (Juli 1993), S. 177-194.
[5] Martin Dietzfelbinger. Primality testing in polynomial time. From Randomized Algorithms to ”PRIMES is in P”. Berlin New York: Springer, 2004. isbn: 3-540-40344-2.
[6] Paul Erdos und Carl Pomerance. „On the Number of False Witnesses for a Composite Number“. In: Mathematics of Computation 46.173 (Jan. 1986), S. 259-279.
[7] P. Kiss, B. M. Phong und E. Lieuwens. „Fibonacci Numbers and their Applications“. In: Hrsg. von A. N. Philippou, G. E. Bergum und A. F. Horadam. Reidel, 1986. Kap. On Lucas pseudoprimes which are products of s primes, S. 131-139.
[8] Niels Möller. „ Efficient computation of the Jacobi symbol“. In: (17. Juli 2019). arXiv: 1907.07795v1 [cs.DS].
[9] Paulo Ribenboim. Die Welt der Primzahlen : Geheimnisse und Rekorde. Berlin, Heidelberg: Springer-Verlag Berlin Heidelberg, 2011. isbn: 978-3-642-18079-8.
[10] A. Schönhage und V. Strassen. „Schnelle Multiplikation großer Zahlen“. In: Computing 7 (1971), S. 281-292.
[11] R. Solovay und V. Strassen. „A Fast Monte-Carlo Test For Primality“. In: SIAM J. Comput. 6(1) (1977), S. 84-85.
[12] William Stein. Elementary number theory : primes, congruences, and secrets. New York London: Springer, 2009. isbn: 978-0-387-85525-7.
[13] Rebecca Waldecker und Lasse Rempe-Gillen. Primzahltests für Einsteiger. Springer, 2016.
[...]
1 Anders ausgedrückt: Für beliebige Ganzzahlen a, b mit a = 0 (mod b) ist (a ) = ( a/b ) * (nb )
2 Dieser Zeuge gibt uns allerdings keinen Aufschluss darüber, wie die Zahl n zu faktorisieren ist!
3 In der eindeutigen Primfaktorzerlegung von n tritt kein Primfaktor mehrfach auf
4 nachzulesen unter anderem in [13, S. 70]
6 eigentlich: eine polynomiell zeitbeschränkte probabilistische Turingmaschine, das formale Berechnungsmodell zu probabilistischen/randomisierten Algorithmen
7 Die für Quadrierungen benötigte Laufzeit kann durch die Verwendung von auf schneller Fourier-Transformation basierenden Algorithmen, wie dem Schönhage-Strassen-Algorithmus, auf O (|| n| |(log || n| |)(loglog || n| |)) gedrückt werden.[10]
8 Bei tiefergehendem Interesse an dem Thema Primzahltests, insbesondere auch an dem weiter oben erwähnten polynomiell zeitbeschränkten deterministischen AKS-Test empfiehlt sich die Lektüre von [13] oder [5].
Buy now
- Quote paper
- Florian Reuss (Author), 2020, Der Solovay-Strassen-Test, Munich, GRIN Verlag, https://www.grin.com/document/1706784
