Solovay-Strassen-Test

Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 30. Juli 2005 um 15:36 Uhr durch Zaph (Diskussion | Beiträge) (Satz wieder eingefügt, Notation im Beispiel angepasst). Sie kann sich erheblich von der aktuellen Version unterscheiden.

Der Solovay-Strassen-Test (nach Robert Solovay und Volker Strassen) ist ein probabilistischer Primzahltest. Der Test prüft für eine Zahl n, ob sie eine Primzahl oder das Produkt mehrerer Faktoren ist. Für den Fall, dass der Test als Antwort liefert, dass es sich bei n nicht um eine Primzahl handelt, liefert der Test jedoch im Allgemeinen keinen Faktor der Zahl n.

Der Test ist ein probabilistischer Algorithmus. Das heißt, das Testergebnis kann mit einer gewissen Wahrscheinichkeit falsch sein. Diese Wahrscheinlichkeit kann aber durch hinreichend häufige Wiederholung beliebig gering gering gehalten werden.

Der Test fällt in die Klasse der Monte-Carlo-Algorithmen d. h. für den Test wird ein Zufallsexperiment benötigt.

Er basiert ähnlich wie der Miller-Rabin-Test auf einem Satz, mit dem festgestellt werden kann, ob eine Zahl eine Primzahl ist, oder nicht.

Vorgehensweise

  • Zu einer zu prüfenden Zahl n, von der wir feststellen wollen, ob sie eine Primzahl ist, wird zufällig eine natürliche Zahl a mit 1 < a < n gewählt.
  • Es wird
g := ggT(a,n)
berechnet. Falls g > 1 ist, so ist g ein Teiler von n, und somit ist n keine Primzahl (und der Test ist dann hier beendet).
  • Wenn diese Hürde überwunden ist, wird
 
berechnet. Falls 1 < b < n-1, kann n nach einem Satz von Euler (eine etwas strengere Variante des kleinen Fermatschen Satzes) keine Primzahl sein (und der Test ist dann hier beendet). Ist andererseits b = 1 oder b = n-1, kann es sich bei n um eine Eulersche Pseudoprimzahl handeln, und der folgende Schrit muss noch ausgeführt werden.
j := J(a,n)
berechnet. Falls n eine Primzahl ist, so muss hier j = b gelten. Gilt dies nicht, kann also n keine Primzahl sein (und der Test ist dann hier beendet).
  • Nur für den Fall, dass die Berechnungen nacheinander
g = 1
b = 1 oder b = n-1
j = b
ergeben, liefert der Test, dass n eine Primzahl ist.

Bewertung

  • Liefert der Solovay-Strassen-Test, dass n keine Primzahl ist, so ist diese Aussage korrekt.
  • Liefert der Test als Antwort, dass n eine Primzahl ist, so ist dies jedoch keine Garantie dafür.

Um die Güte des Solovay-Strassen-Tests zu bewerten, muss unterschieden werden, ob n eine Primzahl ist oder nicht.

  • Wenn n eine Primzahl ist, liefert der Test immer das korrekte Ergebnis.
  • Wenn n keine Primzahl ist, ist die Wahrscheinlichket, im ersten Schritt des Tests ein a zu wählen, sodass der Test ein falsches Ergebnis liefert, kleiner als 1/2.

Um die Güte des Tests für Nichtprimzahlen zu erhöhen, wird der Test mit unabhängig gewählten zufälligen a-Werten hinreichend oft wiederholt. Wenn der Test k mal wiederholt wird, dann ist die Wahrscheinlichkeit dass in allen k Wiederholungen das Ergebnis Primzahl lautet (obwohl n keine Primzahl ist), kleiner als  . Dies ist eine pessimistische Schätzung - in den meisten Fällen wird die Güte wesentlich besser sein.

Effizienz

Der Solovay-Strassen-Test ist effizient, da der ggT, die Potenzen und das Jacobi-Symbol effizient berechnet werden können.

Beispiel

Am Beispiel der zusammengesetzten Zahl n = 91 (einer Pseudoprimzahl) werden die möglichen Abläufe des Tests gezeigt:

Ist 91 eine Primzahl?
Fall 1: a = 7 Fall 2: a=23 Fall 3: a= 17 Fall 4: a=29
g = ggT(7,91) = 7
=>
keine Primzahl
g = ggT(23,91) = 1
b =   mod 91 = 64
=>
keine Primzahl
g = ggT(17,91) = 1
b =   mod 91 = 90 = -1
j = J(17,91) = 1
j   b
=>
keine Primzahl
g = ggT(29,91) = 1
b =   mod 91 = 1
j = J(29,91) = 1
j = b
=>
91 ist eine Primzahl

Die Wahrscheinlichkeit an:

  • Fall 1 zu scheitern beträgt bei 91 ca. 20%
  • Fall 2 zu scheitern beträgt bei 91 ca. 61%
  • Fall 3 zu scheitern beträgt bei 91 ca. 9% (geschätzt)

Falsche Zeugen

Sei   eine ungerade, Nicht-Primzahl. Eine Zahl   mit   heißt falscher Zeuge für die Primalität von   bezüglich des Solovay-Strassen-Tests, falls

 

Die Menge der falschen Zeugen bildet eine Untergruppe zur multiplikativen Gruppe   mit Ordnung   (  bezeichnet die Eulersche_φ-Funktion von N).

Das heißt höchstens die Hälfte aller zur Auswahl stehender Zahlen sind falsche Zeugen.

  1. Durch Zufall wurde ein Faktor gefunden und die Zahl damit als nicht prim identifiziert.
  2. Das Testkriterium wird nicht erfüllt und mittels des Satzes folgt, dass es sich bei der Zahl um keine Primzahl handeln kann.
  3. Das Testkriterium wird erfüllt. Bei der Zahl handelt es sich nach   erfolgreichen Durchgängen höchstens mit einer Wahrscheinlichkeit von   um eine Nicht-Primzahl