Könnte mir jemand ein Beispiel geben wie man beim Miller Rabin Primzahltest zu einer Zahl n (z.B. 61) vorgeht…
wenn ich google finde ich nur Programmiercode und Beweise… Lemma 2.1 und 2.2 habe ich mir angeschaut… aber ich brauch ein Beispiel um das zu verstehen…
Wäre für jede Hilfe dankbar!!!
Könnte mir jemand ein Beispiel geben wie man beim Miller Rabin
Primzahltest zu einer Zahl n (z.B. 61) vorgeht…
Hallo,
du willst n=61 testen, d.h. du zerlegst n-1=60 in seinen geraden und seinen ungeraden Anteil. Das bedeutet im Prinzip, dass du die höchste 2er-Potenz suchst die noch Faktor von n-1 ist.
4 steckt in 60 drin, 8 schon nicht mehr, also
60=15⋅22
Damit ist d=15. (das d aus dem Wikipedia-Artikel)
Jetzt wählst du a zufällig aus 2,3,…,n-1.
Sagen wir mal du wählst a=8.
Im nullten Schritt geht es los mit ad, also 815=50
Ab dem ersten Schritt wird dann immer quadriert, 502=60.
Zweiter Schritt: 602=1
Damit ist der Test fertig, denn 12=1, da wird sich nix mehr ändern.
Auch wenn irgendwann -1 rauskommt ist der Test fertig, denn (-1)2=1.
In diesem Beispiel ist klar, dass im zweiten Schritt 1 rauskommt, denn die höchste 2er-Potenz die wir aus 60 rausziehen konnten war 22.
Angenommen n wäre 89. Dann hätten wir n-1=88=11⋅23, das heißt spätestens im dritten Schritt kommt 1 raus.
Allgemein zerlegst du n-1=d⋅2 j.
Wenn dann bis zum j-ten Schritt (wobei man mit dem nullten Schritt beginnt) weder 1 noch -1 raukommen, dann kann n keine Primzahl sein.
Falls irgendwann 1 oder -1 rauskommt, dann ist n eine Primzahl oder eine starke Pseudoprimzahl (also wahrscheinlich eine Primzahl).
Ich hoffe, das hilft dir ein bisschen, den Test zu verstehen.
Gruß
hendrik
ja danke sofort verstanden =D
modulo regeln
Ich bräuchte da doch noch Hilfe…
Es entstehen ja extrem große Zahlen bei den Rechnungen und mein Taschenrechner hat keine modulo-Taste. Gibt es irgendwelche Rechenregeln um besser mit solchen modulo aufgaben zu rechnen?
z.B. wenn d=25 ist und ich a=3 wähle…
3^25 mod 101 = laut google = 10
= modulo rechner = 26 (http://www.coufal.biz/rechner.shtml)
und wenn ich die probe mache mit meinem Taschenrechner:
(3^25)-10
_________ = 8388996133
101
(3^25)-26
_________ = 8388996133
101
kommt bei beiden Resten das gleiche raus… geht doch gar net
deswegen dachte ich, ich mach aus 3^25 mod 101 = ((3^5)^5) mod 101
aber dann weiß ich halt nicht weiter… da kommt ja bestimmt nicht
(243)^5 mod 101 hin, oder?!
schon gelöst
Hab die Antwort gefunden, obwohl das alles schon ziemlich verwirrend ist…
Modulo regeln:
(a+b)mod n = (a mod n + b mod n) mod n
(a*b) mod n = (a mod n * b mod n) mod n
d.h. für 3^25 mod 101
3^25= 3^5 * 3^5 * 3^5 * 3^5 * 3^5 = (3^5)^5
3^25 mod 101 =
(3^5 mod 101 * 3^5 mod 101 * 3^5 mod 101 * 3^5 mod 101 * 3^5 mod 101) mod 101 =
(41 * 41 * 41 * 41 * 41) mod 101 = 41^5 mod 101 = 10
41^5 mod 101 lässt sich gerade so noch mit einem einfachen Taschenrechner lösen.