Hintergrundwissen
Der SOLOVAY-STRASSEN Primzahltest
Der SOLOVAY-STRASSEN Primzahltest ist ein probabilistischer Primzahltest. Da hier zusätzlich noch das Jacobi-Symbol berechnet werden muss, ist der Rechenaufwand höher als beim MILLER-RABIN Primzahltest
Der SOLOVAY-STRASSEN Primzahltest prüft mit einer zufälligen teilerfremden Basis 1 < a < n, ob die Eigenschaft des EULER-Kriteriums erfüllt ist:
a(n-1)/2 = (a/n) mod n
Falls nicht, ist n keine Primzahl. Falls ja, ist n entweder eine Primzahl oder nicht. Die Fehlerwahrscheinlichkeit kann abgeschätzt werden duch:
<= 1/2
Wiederholt man den Test k-mal mit unabhängigen Zufallszahlen, reduziert sich die Fehlerwahrscheinlichkeit auf (1/2)k.