Frage zum Miller-Rabin-Test

[Senior Sanchez]

Hoi,

Joar, ich beschäftige mich gerade mit dem Miller-Rabin-Test und da ist mir was aufgefallen. Der kleine Satz von Fermat ist ja klar, aber den zweiten Test, da verstehe ich was nicht.

Und zwar ist laut folgender Seite http://de.wikipedia.org/wiki/Miller-Rabin-Test ja als zweiter Test durchzuführen, ob a^(d*2^r) mod n = -1 ist, wenn ich das richtig interpretiere.
Aber ist laut Definition der Modulo-Operation der Rest denn nicht immer positiv? Das ist doch eine Forderung. Oder verstehe ich da gerade etwas falsch?

Danke schonmal

[Trap]

Das mod bezieht sich auf beide Seiten der Gleichung. -1 mod n = n-1

[Senior Sanchez]

Das mod bezieht sich auf beide Seiten der Gleichung. -1 mod n = n-1

Ich weiß jetzt nicht, ob ich dich richtig verstehe, aber im Grunde soll das dann aussagen, dass a^(d*2^r) mod n als Rest (n-1) lassen soll? Ich blicke das gerade irgendwie nicht.

[Gnafoo]

Genau. (-1) und (n-1) liegen ja in der selben Restklasse von Z_n. Also ist (-1 = n-1) mod n. Ich hab vor kurzem auch etwas mit Miller-Rabin rumgespielt. Da hat mir das folgende Dokument (gefunden mit Google) ganz gut weitergeholfen:
http://www.bitnuts.de/rienhardt/docs/miller_rabin.pdf

[Senior Sanchez]

*disch* stimmt ja, die Äquivalenzklassen ;) Ich vergaß.

Dann ist mir soweit alles klar. Danke für den Link.