imported>Hardy42: /* Was steckt hinter dem Solovay-Strassen-Test? */ Euler-Jacobi-Pseudoprimzahlen bestehen den Test (Korr. Fehler v. 2010)

2023-07-15T14:43:03Z

Was steckt hinter dem Solovay-Strassen-Test?: Euler-Jacobi-Pseudoprimzahlen bestehen den Test (Korr. Fehler v. 2010)

Neue Seite

Der '''Solovay-Strassen-Test''' (nach [[Robert M. Solovay]] und [[Volker Strassen]]) ist ein [[Probabilistischer Algorithmus|probabilistischer]] [[Primzahltest]]. Der Test prüft für eine ungerade Zahl ''n'', ob sie [[Primzahl|prim]] oder [[Zusammengesetzte Zahl|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.

== Vorgehensweise ==
Zu einer ungeraden Zahl <math>n</math>, welche auf Primzahleigenschaft zu testen ist, wird zufällig eine natürliche Zahl <math>a</math> mit <math>1<a<n</math> gewählt. Bei mehrfacher Durchführung des Tests sind für <math>a</math> jeweils neue Werte zu wählen.
* Es wird der [[ggT|größte gemeinsame Teiler]] <math>g := \operatorname{ggT}(a,n)</math> berechnet. Falls <math>g > 1</math> gilt, so ist <math>g</math> ein echter Teiler von <math>n</math>. Damit ist <math>n</math> keine Primzahl und der Test wird beendet.
* Berechne
:: <math>b := a^{\frac{n-1}{2}} \mod n</math>
: Gilt <math>1 < b < n-1</math>, so kann <math>n</math> nach dem [[Kleiner Fermatscher Satz#Folgerung durch Euler|Satz von Euler]] keine Primzahl sein und der Test wird beendet. Ist aber <math>b=1</math> oder <math>b=n-1</math>, kann es sich bei <math>n</math> um eine [[Eulersche Pseudoprimzahl]] handeln und der folgende Schritt muss noch ausgeführt werden.
* Berechne das [[Jacobi-Symbol]] <math>J(a,n)</math>. Falls <math>n</math> eine Primzahl ist, so muss <math>J(a,n)\equiv b\ mod\ n</math> gelten. Gilt dies nicht, kann <math>n</math> keine Primzahl sein und der Test ist beendet.
* Falls die Berechnungen nacheinander <math>g = 1, b = 1</math> oder <math>b = n-1, J(a,n)\equiv b\ mod\ n</math> ergeben, liefert der Solovay-Strassen-Test keine Aussage, <math>n</math> ist also eventuell eine Primzahl.

== Bewertung ==
Um die Güte des Solovay-Strassen-Tests zu bewerten, muss unterschieden werden, ob <math>n</math> eine Primzahl ist oder nicht.
* Falls <math>n</math> eine Primzahl ist, liefert der Test ''immer'' das korrekte Ergebnis (nämlich „keine Aussage“).
* Falls <math>n</math> keine Primzahl ist, ist die Wahrscheinlichkeit, im ersten Schritt des Tests ein <math>a</math> 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 <math>a</math> hinreichend oft wiederholt. Wenn der Test <math>k</math>-mal wiederholt wird, dann ist die Wahrscheinlichkeit, dass in allen <math>k</math> Wiederholungen das Ergebnis „keine Aussage“ lautet (obwohl <math>n</math> keine Primzahl ist), kleiner als <math>1/2^k</math>. 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 <math>n = 91</math> (einer [[Fermatsche Pseudoprimzahl|Fermatschen Pseudoprimzahl]] zu – beispielsweise – den Basen 17, 29) wird ein möglicher Ablauf des Tests gezeigt:

Ist 91 eine Primzahl?

Test 1:<math>a = 29</math>
:<math>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 }</math>

Test 2: <math>a = 17</math>
:<math>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}</math>


Test 3: <math>a = 23</math>
:<math>g = \operatorname{ggT}(23,91) = 1,\,\, b = 23^{45} \equiv 64 (\text{mod }\, 91) \implies \text{keine Primzahl}</math>

== Falsche Zeugen ==
Sei n > 2 eine ungerade, zusammengesetzte Zahl.<br>
Eine zu <math>n</math> teilerfremde Zahl <math>a</math> heißt ''falscher Zeuge'' für die Primalität von <math>n</math> bezüglich des Solovay-Strassen-Tests, falls
:<math>a^{\frac{n-1}{2}} \equiv J(a,n) \mod n</math>.
Für <math>n = 91</math> sind also die Basen <math>a = 17, 29</math> falsche Zeugen. Da die Menge der falschen Zeugen eine Untergruppe der [[Multiplikative Gruppe|multiplikativen Gruppe]] <math>(\mathbb{Z}/n)^*</math> mit [[Gruppenordnung|Ordnung]] kleiner oder gleich <math>\frac{\varphi(n)}{2}</math> bildet (dabei bezeichnet <math>\varphi</math> die [[Eulersche φ-Funktion]], die die Anzahl der teilerfremden Zahlen kleiner als <math>n</math> angibt) und <math>\varphi(n) < n</math> gilt, sind höchstens die Hälfte aller zur Auswahl stehenden Basen <math>a</math> falsche Zeugen. Daher erreicht man bei <math>k</math> Durchläufen eine Wahrscheinlichkeit für einen Fehler (d. h., eine zusammengesetzte Zahl wird nicht als solche erkannt), die kleiner als <math>1/2^k</math> ist.

== Was steckt hinter dem Solovay-Strassen-Test? ==
Der Solovay-Strassen-Test beruht auf zwei Primzahl-Eigenschaften:

Die eine ist der [[Kleiner fermatscher Satz#Folgerung durch Euler|Eulersche Satz]]: Für jede Primzahl ''p'' > 2 gilt
: <math>a^{\frac{p-1}{2}} \equiv \pm 1 \pmod p</math> .
Mit diesem Kriterium werden alle Zahlen herausgesiebt, die weder [[Primzahl]]en noch [[Eulersche Pseudoprimzahl]]en zur Basis ''a'' sind.

Die andere Eigenschaft verbindet dies mit dem [[Legendre-Symbol]]: Für jede Primzahl ''p'' > 2 gilt
: <math>a^{\frac{p-1}{2}} \equiv \Big(\frac{a}{p}\Big)\pmod p</math> .
Da man bei den zu testenden Zahlen nicht davon ausgehen darf, dass es sich um Primzahlen handelt, benutzt man das [[Jacobi-Symbol]].<br>
Damit fallen auch jene eulerschen Pseudoprimzahlen raus, für die <math>a^{\frac{n-1}{2}} \equiv \left(\frac{a}{n}\right) \pmod n</math> nicht gilt; es bleiben nur noch Primzahlen und [[Eulersche Pseudoprimzahl#Definition|Euler-Jacobi-Pseudoprimzahlen]] übrig.

== Literatur ==
* [[Paulo Ribenboim]]: ''Die Welt der Primzahlen'', Springer Verlag, 1996, S. 97

[[Kategorie:Zahlentheoretischer Algorithmus]]

Solovay-Strassen-Test - Versionsgeschichte

imported>Hardy42: /* Was steckt hinter dem Solovay-Strassen-Test? */ Euler-Jacobi-Pseudoprimzahlen bestehen den Test (Korr. Fehler v. 2010)