www.wikidata.de-de.nina.az

Solovay Strassen Test Der nach Robert M Solovay und Volker Strassen ist ein probabilistischer Primzahltest Der Test prüf

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.

Vorgehensweise Bearbeiten

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.

Bewertung Bearbeiten

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.

Effizienz Bearbeiten

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

Beispiel Bearbeiten

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 Zeugen Bearbeiten

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.
Damit fallen auch jene eulerschen Pseudoprimzahlen raus, für die nicht gilt; es bleiben nur noch Primzahlen und Euler-Jacobi-Pseudoprimzahlen übrig.

Literatur Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Solovay Strassen Test nach Robert M Solovay und Volker Strassen ist ein probabilistischer Primzahltest Der Test pruft fur 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 heisst er liefert nur mit einer gewissen Wahrscheinlichkeit 50 eine Aussage Durch Wiederholung kann diese Wahrscheinlichkeit aber beliebig vergrossert werden Ergibt der Test wiederholt keine Aussage so lasst sich dies als n ist wahrscheinlich eine Primzahl interpretieren Inhaltsverzeichnis 1 Vorgehensweise 2 Bewertung 3 Effizienz 4 Beispiel 5 Falsche Zeugen 6 Was steckt hinter dem Solovay Strassen Test 7 LiteraturVorgehensweise BearbeitenZu einer ungeraden Zahl n displaystyle n nbsp welche auf Primzahleigenschaft zu testen ist wird zufallig eine naturliche Zahl a displaystyle a nbsp mit 1 lt a lt n displaystyle 1 lt a lt n nbsp gewahlt Bei mehrfacher Durchfuhrung des Tests sind fur a displaystyle a nbsp jeweils neue Werte zu wahlen Es wird der grosste gemeinsame Teiler g ggT a n displaystyle g operatorname ggT a n nbsp berechnet Falls g gt 1 displaystyle g gt 1 nbsp gilt so ist g displaystyle g nbsp ein echter Teiler von n displaystyle n nbsp Damit ist n displaystyle n nbsp keine Primzahl und der Test wird beendet Berechneb a n 1 2 mod n displaystyle b a frac n 1 2 mod n nbsp dd Gilt 1 lt b lt n 1 displaystyle 1 lt b lt n 1 nbsp so kann n displaystyle n nbsp nach dem Satz von Euler keine Primzahl sein und der Test wird beendet Ist aber b 1 displaystyle b 1 nbsp oder b n 1 displaystyle b n 1 nbsp kann es sich bei n displaystyle n nbsp um eine Eulersche Pseudoprimzahl handeln und der folgende Schritt muss noch ausgefuhrt werden Berechne das Jacobi Symbol J a n displaystyle J a n nbsp Falls n displaystyle n nbsp eine Primzahl ist so muss J a n b m o d n displaystyle J a n equiv b mod n nbsp gelten Gilt dies nicht kann n displaystyle n nbsp keine Primzahl sein und der Test ist beendet Falls die Berechnungen nacheinander g 1 b 1 displaystyle g 1 b 1 nbsp oder b n 1 J a n b m o d n displaystyle b n 1 J a n equiv b mod n nbsp ergeben liefert der Solovay Strassen Test keine Aussage n displaystyle n nbsp ist also eventuell eine Primzahl Bewertung BearbeitenUm die Gute des Solovay Strassen Tests zu bewerten muss unterschieden werden ob n displaystyle n nbsp eine Primzahl ist oder nicht Falls n displaystyle n nbsp eine Primzahl ist liefert der Test immer das korrekte Ergebnis namlich keine Aussage Falls n displaystyle n nbsp keine Primzahl ist ist die Wahrscheinlichkeit im ersten Schritt des Tests ein a displaystyle a nbsp zu wahlen so dass der Test ein falsches Ergebnis liefert kleiner als 1 2 siehe unten Falsche Zeugen Um die Gute des Tests fur Nichtprimzahlen zu erhohen wird der Test mit unabhangig gewahlten zufalligen Basen a displaystyle a nbsp hinreichend oft wiederholt Wenn der Test k displaystyle k nbsp mal wiederholt wird dann ist die Wahrscheinlichkeit dass in allen k displaystyle k nbsp Wiederholungen das Ergebnis keine Aussage lautet obwohl n displaystyle n nbsp keine Primzahl ist kleiner als 1 2 k displaystyle 1 2 k nbsp Dies ist eine pessimistische Schatzung in den meisten Fallen wird die Gute wesentlich besser sein Effizienz BearbeitenDer Solovay Strassen Test ist effizient da der ggT die Potenzen und das Jacobi Symbol effizient berechnet werden konnen Beispiel BearbeitenAm Beispiel der zusammengesetzten Zahl n 91 displaystyle n 91 nbsp einer Fermatschen Pseudoprimzahl zu beispielsweise den Basen 17 29 wird ein moglicher Ablauf des Tests gezeigt Ist 91 eine Primzahl Test 1 a 29 displaystyle a 29 nbsp g ggT 29 91 1 b 29 45 1 mod 91 J 29 91 1 b mod 91 Primzahl nicht ausgeschlossen 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 nbsp Test 2 a 17 displaystyle a 17 nbsp g ggT 17 91 1 b 17 45 1 mod 91 J 17 91 1 b mod 91 Primzahl nicht ausgeschlossen 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 nbsp Test 3 a 23 displaystyle a 23 nbsp g ggT 23 91 1 b 23 45 64 mod 91 keine Primzahl displaystyle g operatorname ggT 23 91 1 b 23 45 equiv 64 text mod 91 implies text keine Primzahl nbsp Falsche Zeugen BearbeitenSei n gt 2 eine ungerade zusammengesetzte Zahl Eine zu n displaystyle n nbsp teilerfremde Zahl a displaystyle a nbsp heisst falscher Zeuge fur die Primalitat von n displaystyle n nbsp bezuglich des Solovay Strassen Tests falls a n 1 2 J a n mod n displaystyle a frac n 1 2 equiv J a n mod n nbsp Fur n 91 displaystyle n 91 nbsp sind also die Basen a 17 29 displaystyle a 17 29 nbsp falsche Zeugen Da die Menge der falschen Zeugen eine Untergruppe der multiplikativen Gruppe Z n displaystyle mathbb Z n nbsp mit Ordnung kleiner oder gleich f n 2 displaystyle frac varphi n 2 nbsp bildet dabei bezeichnet f displaystyle varphi nbsp die Eulersche f Funktion die die Anzahl der teilerfremden Zahlen kleiner als n displaystyle n nbsp angibt und f n lt n displaystyle varphi n lt n nbsp gilt sind hochstens die Halfte aller zur Auswahl stehenden Basen a displaystyle a nbsp falsche Zeugen Daher erreicht man bei k displaystyle k nbsp Durchlaufen eine Wahrscheinlichkeit fur einen Fehler d h eine zusammengesetzte Zahl wird nicht als solche erkannt die kleiner als 1 2 k displaystyle 1 2 k nbsp ist Was steckt hinter dem Solovay Strassen Test BearbeitenDer Solovay Strassen Test beruht auf zwei Primzahl Eigenschaften Die eine ist der Eulersche Satz Fur jede Primzahl p gt 2 gilt a p 1 2 1 mod p displaystyle a frac p 1 2 equiv pm 1 pmod p nbsp 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 Fur jede Primzahl p gt 2 gilt a p 1 2 a p mod p displaystyle a frac p 1 2 equiv Big frac a p Big pmod p nbsp 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 fur die a n 1 2 a n mod n displaystyle a frac n 1 2 equiv left frac a n right pmod n nbsp nicht gilt es bleiben nur noch Primzahlen und Euler Jacobi Pseudoprimzahlen ubrig Literatur BearbeitenPaulo Ribenboim Die Welt der Primzahlen Springer Verlag 1996 S 97 Abgerufen von https de wikipedia org w index php title Solovay Strassen Test amp oldid 235501987