miller-rabin-test
-
Man hat die volgenden Werte gegeben, aber ich habe nicht verstanden, warum mann a zufällig bestimmen kann und aus welchen bereich die zahl sein muss und wie man auf die 44 beim ersten test kommt.
ich hoffe ,mir kann das jemand erklären.gruß gucky
n = 149; n – 1 = 148; S = 2; d = 37; a = 14; r = {0,1}
Schritt 5:
a zufällig bestimmen a = 14
Schritt 6:1. Test: a^d ≡ 1 mod n
14^37 ≡ 44 mod 149 -> nicht bestanden
-
Gucky schrieb:
warum mann a zufällig bestimmen kann
Das ist eher eine Verlegenheitslösung, da man nicht weiß wie man das a besser bestimmen könnte. Da man auch zufällig ein schlechtes a wählen könnte, wiederholt man den Test mehrmals. Da die Chance recht gering ist, mehrmals ein schlechtes a zu wählen, kommt man recht schnell zu einer akzeptablen Wahrscheinlichkeit, dass das Ergebnis richtig ist.
und aus welchen bereich die zahl sein muss
a<n
und wie man auf die 44 beim ersten test kommt.
Rechnen
. Ok, 14^37 ist nicht ganz so trivial, ich seh's ein 
. Daher schicke ich dich mal zur Wikipedia:http://en.wikipedia.org/wiki/Modular_exponentiation
http://en.wikipedia.org/wiki/Square-and-multiply_algorithm
-
vielleicht könnte mir das jemand versuchen zu erklären, weil in der 10. klasse macht man so etwas nicht umbedingt
-
Gucky schrieb:
vielleicht könnte mir das jemand versuchen zu erklären, weil in der 10. klasse macht man so etwas nicht umbedingt
Ihr macht das in der 10. Klasse?
Bist du auf einer Schule für Hochbegabte? Das ist nämlich eher fortgeschrittener (3.-4. Semester) Unistoff. Da die 10. Klasse schon etwas länger her ist, kann ich mich schwer in dich reinversetzen. Daher: Was verstehst du denn schon und was verstehst du nicht? Keine Scheu vor scheinbar dummen Fragen (zum Beispiel was das Gleichheitszeichen mit 3 Strichen bedeutet, falls dir das nicht klar sein sollte).
-
ich meinte damit, das eich davon keine ahnung habe und mir jemand vielleicht erklären könnte warum das so ist bzw. wie das geht
-
Ich muss die Anwendung des Algorithmus im Zusammenhang mit Monte Carlo-Verfahren gerade an der Universität durchnehmen.
Du kannst das a deshalb zufällig bestimmen, weil der Miller-Rabin-Test kein 100%iges Ergebnis liefert. Du überprüfst nur s Mal hintereinander ob eine bestimmte Bedingung mit einer zufälligen Zahl erfüllt ist und kannst dann nach s Überprüfungen sagen, dass dein Ergebnis die maximale Fehlerrate 1/(2^s) hat.
Die Zahl a muss aus dem Bereich {1, ..., n-1} sein.
Wie gesagt, das Ergebnis "stimmt" nur bis zu einer gewissen Wahrscheinlichkeit. Bspw. gibt es sogenannte "Carmichael-Zahlen" die die Bedingung für alle a erfüllen, dennoch aber keine Primzahlen sind.
Damit du die Bedingung (a^(n-1) ≡ 1 mod n) schnell überprüfen kannst hat dir Sepp schon zwei Wiki-Links geposted.
MfG SideWinder
-
Gucky schrieb:
ich meinte damit, das eich davon keine ahnung habe und mir jemand vielleicht erklären könnte warum das so ist bzw. wie das geht
Das Verfahren basiert auf dem Satz von Fermat der besagt:
Sei n eine Primzahl, so gilt für alle a € { 1, ..., n-1 } die Bedingung: an-1 ≡ 1 mod n
Wenn du auch dafür noch gerne einen Beweis haben möchtest, dann verweise ich dich mal an Wikipedia. Ich studiere nur Informatik und nicht Mathematik. Ich glaube soetwas
MfG SideWinder
-
ok, das mit dem a hab ich verstanden, aber in meinem beispiel war nicht a^n-1 ≡ 1 mod n, sondern a^d ≡ 1 mod n (d ist (n-1) / 2^s und s ist der exponent ,der (n - 1) % 2^s = 0 ergibt )
hier meine quelle http://www.wi.uni-muenster.de/pi/lehre/ws0708/seminar/Pr%C3%A4sentationen/Primzahlerzeugung.pdf
