Solovay-Strassen-Test

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

• Es wird der größte gemeinsame Teiler ${\displaystyle g:=\operatorname {ggT} (a,n)}$ berechnet. Falls ${\displaystyle g>1}$ gilt, so ist ${\displaystyle g}$ ein echter Teiler von ${\displaystyle n}$. Damit ist ${\displaystyle n}$ keine Primzahl und der Test wird beendet.
• Berechne

${\displaystyle b:=a^{\frac {n-1}{2}}\mod n}$

Gilt ${\displaystyle 1<b<n-1}$, so kann ${\displaystyle n}$ nach dem Satz von Euler keine Primzahl sein und der Test wird beendet. Ist aber ${\displaystyle b=1}$ oder ${\displaystyle b=n-1}$, kann es sich bei ${\displaystyle n}$ um eine Eulersche Pseudoprimzahl handeln und der folgende Schritt muss noch ausgeführt werden.

• Berechne das Jacobi-Symbol ${\displaystyle J(a,n)}$. Falls ${\displaystyle n}$ eine Primzahl ist, so muss ${\displaystyle J(a,n)\equiv b\ mod\ n}$ gelten. Gilt dies nicht, kann ${\displaystyle n}$ keine Primzahl sein und der Test ist beendet.
• Falls die Berechnungen nacheinander ${\displaystyle g=1,b=1}$ oder ${\displaystyle b=n-1,J(a,n)\equiv b\ mod\ n}$ ergeben, liefert der Solovay-Strassen-Test keine Aussage, ${\displaystyle n}$ ist also eventuell eine Primzahl.

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

• Falls ${\displaystyle n}$ eine Primzahl ist, liefert der Test immer das korrekte Ergebnis (nämlich „keine Aussage“).
• Falls ${\displaystyle n}$ keine Primzahl ist, ist die Wahrscheinlichkeit, im ersten Schritt des Tests ein ${\displaystyle a}$ 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 ${\displaystyle a}$ hinreichend oft wiederholt. Wenn der Test ${\displaystyle k}$-mal wiederholt wird, dann ist die Wahrscheinlichkeit, dass in allen ${\displaystyle k}$ Wiederholungen das Ergebnis „keine Aussage“ lautet (obwohl ${\displaystyle n}$ keine Primzahl ist), kleiner als ${\displaystyle 1/2^{k}}$. Dies ist eine pessimistische Schätzung – in den meisten Fällen wird die Güte wesentlich besser sein.

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

Am Beispiel der zusammengesetzten Zahl ${\displaystyle n=91}$ (einer Fermatschen Pseudoprimzahl zu – beispielsweise – den Basen 17, 29) wird ein möglicher Ablauf des Tests gezeigt:

Ist 91 eine Primzahl?

Test 1:${\displaystyle a=29}$

${\displaystyle g=\operatorname {ggT} (29,91)=1,\,\,b=29^{45}\equiv 1({\text{mod }}\,91),\,\,J(29,91)=1\equiv b{\text{ mod }}91\implies {\text{ Primzahl nicht ausgeschlossen }}}$

Test 2: ${\displaystyle a=17}$

${\displaystyle g=\operatorname {ggT} (17,91)=1,\,\,b=17^{45}\equiv -1({\text{mod }}\,91),\,\,J(17,91)=-1\equiv b{\text{ mod }}91\implies {\text{Primzahl nicht ausgeschlossen}}}$

Test 3: ${\displaystyle a=23}$

${\displaystyle g=\operatorname {ggT} (23,91)=1,\,\,b=23^{45}\equiv 64({\text{mod }}\,91)\implies {\text{keine Primzahl}}}$

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

${\displaystyle a^{\frac {n-1}{2}}\equiv J(a,n)\mod n}$.

Für ${\displaystyle n=91}$ sind also die Basen ${\displaystyle a=17,29}$ falsche Zeugen. Da die Menge der falschen Zeugen eine Untergruppe der multiplikativen Gruppe ${\displaystyle (\mathbb {Z} /n)^{*}}$ mit Ordnung kleiner oder gleich ${\displaystyle {\frac {\varphi (n)}{2}}}$ bildet (dabei bezeichnet ${\displaystyle \varphi }$ die Eulersche φ-Funktion, die die Anzahl der teilerfremden Zahlen kleiner als ${\displaystyle n}$ angibt) und ${\displaystyle \varphi (n)<n}$ gilt, sind höchstens die Hälfte aller zur Auswahl stehenden Basen ${\displaystyle a}$ falsche Zeugen. Daher erreicht man bei ${\displaystyle k}$ Durchläufen eine Wahrscheinlichkeit für einen Fehler (d. h., eine zusammengesetzte Zahl wird nicht als solche erkannt), die kleiner als ${\displaystyle 1/2^{k}}$ ist.

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

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

${\displaystyle a^{\frac {p-1}{2}}\equiv \pm 1{\pmod {p}}}$ .

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

${\displaystyle a^{\frac {p-1}{2}}\equiv {\Big (}{\frac {a}{p}}{\Big )}{\pmod {p}}}$ .

Da man bei den zu testenden Zahlen nicht davon ausgehen darf, dass es sich um Primzahlen handelt, benutzt man das Jacobi-Symbol.
Damit fallen auch jene eulerschen Pseudoprimzahlen raus, für die ${\displaystyle a^{\frac {n-1}{2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}$ nicht gilt; es bleiben nur noch Primzahlen und Euler-Jacobi-Pseudoprimzahlen übrig.

• Paulo Ribenboim: Die Welt der Primzahlen, Springer Verlag, 1996, S. 97