13.Vorlesung - Was ist modulo ?

18/09/2014 - 20:20 von Weltmarktf | Report spam
17 mod 3 = 2, da 17 = 5 mal 3 + 2 ("3 passt fünfmal in 17 und es bleiben 2 übrig" - der Rest ist also 2)

2 mod 3 = 2, da 2 = 0 mal 3 + 2

3 mod 3 = 0, da 3 = 1 mal 3 + 0

Kleiner Fermatscher Satz : Sei p prim dann gilt a p -1 == 1 (mod p ) für alle a aus {1 ... p - 1}
Auf diesem Satz beruht der Fermatsche Primzahltest .

Für jede Primzahl p und jede dazu teilerfremde natürliche Zahl a ist folgende Kongruenz erfüllt:
a^{p-1} = 1 mod p .
Durch Umkehrung dieser Bedingung kann man für natürliche Zahlen testen, ob sie zusammengesetzt sind. Ist nàmlich a^{n-1} - 1 für eine zu n teilerfremde Basis a nicht durch n teilbar, so kann n nicht prim sein. Zum Beispiel kann man aus 28 = 256 = 28·9 + 4 ≡ 4 mod 9 schließen, dass die Zahl 9 zusammengesetzt ist.
Der fermatsche Primzahltest verlàuft so:
Eingabe: n: zu testende natürliche Zahl, Ergebnis: zusammengesetzt oder keine Aussage
Wàhle eine Basis a mit 1 < a < n aus. Prüfe, ob n und a teilerfremd sind.
Wenn sie nicht teilerfremd sind, dann ist das Ergebnis zusammengesetzt. Ansonsten:
Wenn a^{n-1} <> 1 mod n, dann ist das Ergebnis zusammengesetzt.
Sonst ist das Ergebnis keine Aussage
Wird der Test mehrfach mit unterschiedlichen Basen wiederholt, so ist keine Aussage interpretierbar als vermutlich Primzahl.

Wenn ich den Miller-Rabin-Test nehme dann habe ich mit starken Pseudoprimzahlen
zu kàmpfen.

Mit was habt ihr zu kàmpfen ?

Mit eurem Hüftgold ?


Fermatscher Primzahltest kleiner fermatscher Satz Fermatsche Pseudoprimzahlen

Solovay-Strassen-Test Satz von Euler und Jacobi-Symbol Eulersche Pseudoprimzahlen

Miller-Rabin-Test Satz nach Miller starke Pseudoprimzahlen

-

Ihr konntet ja diese Woche hier die Zahl von Curtis Cooper ( " Dirty Curty " ) anschauen.

Welchen Test hat er wohl verwendet ?

Ich vermute ja fast US-Millionàr Dirty Curty hat 1000 von seinen Studenten viel Geld gegeben damit sie seine Primzahl mit ihren eigenen Intel 386 PCs testen.
 

Lesen sie die antworten

#1 IV
20/09/2014 - 20:48 | Warnen spam
"Weltmarktführer" schrieb im Newsbeitrag
news:
Wenn ich den Miller-Rabin-Test nehme dann habe ich mit starken
Pseudoprimzahlen zu kàmpfen.
Mit was habt ihr zu kàmpfen ?
Mit eurem Hüftgold ?


(Mit "Weltmarktführer" - "mit" nicht im Sinne von "gemeinsam", sondern in
der Bedeutung von "gegen". Und das aus gutem Grund! Wie man auch hier wieder
sieht!

Ähnliche fragen