Solovay-Strassen-Test

Der Solovay-Strassen-Test (nach Robert M. Solovay und Volker Strassen) ist ein probabilistischer Primzahltest. Der Test prüft für eine ungerade Zahl n, ob sie prim oder zusammengesetzt ist. Im letzteren Fall liefert der Test jedoch im Allgemeinen keinen Faktor der Zahl n.

Der Solovay-Strassen-Test ist, wie der Miller-Rabin-Test, ein Monte-Carlo-Algorithmus. Das heißt, er liefert nur mit einer gewissen Wahrscheinlichkeit (50 %) eine Aussage. Durch Wiederholung kann diese Wahrscheinlichkeit aber beliebig vergrößert werden. Ergibt der Test (wiederholt) keine Aussage, so lässt sich dies als „n ist wahrscheinlich eine Primzahl“ interpretieren.

VorgehensweiseBearbeiten

Zu einer ungeraden Zahl  , welche auf Primzahleigenschaft zu testen ist, wird zufällig eine natürliche Zahl   mit   gewählt. Bei mehrfacher Durchführung des Tests sind für   jeweils neue Werte zu wählen.

  • Es wird der größte gemeinsame Teiler   berechnet. Falls   gilt, so ist   ein echter Teiler von  . Damit ist   keine Primzahl und der Test wird beendet.
  • Berechne
 
Gilt  , so kann   nach dem Satz von Euler keine Primzahl sein und der Test wird beendet. Ist aber   oder  , kann es sich bei   um eine Eulersche Pseudoprimzahl handeln und der folgende Schritt muss noch ausgeführt werden.
  • Berechne das Jacobi-Symbol  . Falls   eine Primzahl ist, so muss   gelten. Gilt dies nicht, kann   keine Primzahl sein und der Test ist beendet.
  • Falls die Berechnungen nacheinander   oder   ergeben, liefert der Solovay-Strassen-Test keine Aussage,   ist also eventuell eine Primzahl.

BewertungBearbeiten

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

  • Falls   eine Primzahl ist, liefert der Test immer das korrekte Ergebnis (nämlich „keine Aussage“).
  • Falls   keine Primzahl ist, ist die Wahrscheinlichkeit, im ersten Schritt des Tests ein   zu wählen, so dass der Test ein falsches Ergebnis liefert, kleiner als 1/2 (siehe unten: Falsche Zeugen).

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

EffizienzBearbeiten

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

BeispielBearbeiten

Am Beispiel der zusammengesetzten Zahl   (einer Fermatschen Pseudoprimzahl zu – beispielsweise – den Basen 17, 29) wird ein möglicher Ablauf des Tests gezeigt:

Ist 91 eine Primzahl?

Test 1: 

 

Test 2:  

 

Test 3:  

 

Falsche ZeugenBearbeiten

Sei n > 2 eine ungerade, zusammengesetzte Zahl.
Eine zu   teilerfremde Zahl   heißt falscher Zeuge für die Primalität von   bezüglich des Solovay-Strassen-Tests, falls

 .

Für   sind also die Basen   falsche Zeugen. Da die Menge der falschen Zeugen eine Untergruppe der multiplikativen Gruppe   mit Ordnung kleiner oder gleich   bildet (dabei bezeichnet   die Eulersche φ-Funktion, die die Anzahl der teilerfremden Zahlen kleiner als   angibt) und   gilt, sind höchstens die Hälfte aller zur Auswahl stehenden Basen   falsche Zeugen. Daher erreicht man bei   Durchläufen eine Wahrscheinlichkeit für einen Fehler (d. h., eine zusammengesetzte Zahl wird nicht als solche erkannt), die kleiner als   ist.

Was steckt hinter dem Solovay-Strassen-Test?Bearbeiten

Der Solovay-Strassen-Test beruht auf zwei Primzahl-Eigenschaften:

Die eine ist der Eulersche Satz: Für jede Primzahl p > 2 gilt

  .

Mit diesem Kriterium werden alle Zahlen herausgesiebt, die weder Primzahlen noch Eulersche Pseudoprimzahlen zur Basis a sind.

Die andere Eigenschaft verbindet dies mit dem Legendre-Symbol: Für jede Primzahl p > 2 gilt

  .

Da man bei den zu testenden Zahlen nicht davon ausgehen darf, dass es sich um Primzahlen handelt, benutzt man das Jacobi-Symbol.
Mit diesem Kriterium fallen auch die Euler-Jacobi-Pseudoprimzahlen heraus.

LiteraturBearbeiten