Solovay-Strassen-Test - de.LinkFang.org

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.

Inhaltsverzeichnis

Vorgehensweise


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

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

Bewertung


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

Um die Güte des Tests für Nichtprimzahlen zu erhöhen, wird der Test mit unabhängig gewählten zufälligen Basen a hinreichend oft wiederholt. Wenn der Test k-mal wiederholt wird, dann ist die Wahrscheinlichkeit, dass in allen k Wiederholungen das Ergebnis „keine Aussage“ lautet (obwohl 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.

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 {\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}}}

Falsche Zeugen


Sei n > 2 eine ungerade, zusammengesetzte Zahl.
Eine zu n teilerfremde Zahl a heißt falscher Zeuge für die Primalität von 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 \varphi die Eulersche φ-Funktion, die die Anzahl der teilerfremden Zahlen kleiner als n angibt) und {\displaystyle \varphi (n)<n} gilt, sind höchstens die Hälfte aller zur Auswahl stehenden Basen a falsche Zeugen. Daher erreicht man bei 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.

Was steckt hinter dem Solovay-Strassen-Test?


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\mod 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 )}\mod p} .

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.

Literatur





Kategorien: Zahlentheoretischer Algorithmus



Quelle: Wikipedia - https://de.wikipedia.org/wiki/Solovay-Strassen-Test (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.


Stand der Informationen: 21.10.2019 09:51:26 CEST - Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.