Was ist modulare Multiplikation?
-
Hi,
ich hoffe mal, dass das hier das richtige Forum ist.Also ich studiere Informatik und wir haben folgende Aufgabe:
Schreib eine Funktion die (a^x) mod m (a hoch x) berechnet.
Das soll man dann auf zwei Arten machen und eine davon wäre:Eine iterative Version die einfach x-1 modulare Multiplikationen durchführt.
So, nun frag ich mich, was ist modulare Multiplikation?
hoffe jemand kann helfen
ciao Lord
-
Modulare Multiplikation ist eigentlich ganz einfach.
Wenn Du z.B. (3 mod 7) * (4 mod 7) rechnest, dann bekommst du 12 mod 7 = 5 mod 7.
Du rechnest also eigentlich nur mit den Resten.Bei uns wurde dann immer gesagt: Wir rechnen jetzt in Z3 z.B., da gibt es nur die Zahlen 0, 1, 2. Ganzzahlige Reste der Division durch 3. Und dann ist 1+2 = 3 = 0, da 3/3 den Rest 0 hat.
Hoffe es ist einigermaßen verständlich. Gestern Abend war ein wenig hart für mich.
-
*kopfkratz*
Also wenn ich das jetzt richtig verstanden habe heißt das:
(a mod m)(b mod m)=(ab) mod m
Für die Aufgabe würde das dann heißen
(a^x) mod m=(a mod m)...(x-mal)..(a mod m)?
Wenn ich aber zum Beispiel rechne:
(3 mod 7)(4 mod 7)=34=12
aber (12 mod 7)= 5
Irgendwas habich da wohl noch nit kapiert...
-
12 mod 7 ist das gleiche (oder das selbe?) wie 5 mod 7
sowohl 12 als auch 5 geben bei division durch 7 den rest 5
-
Ja sicher, das is schon richtig aber
(3 mod 7)*(4 mod 7) != (12 mod 7)
<=> 3 * 4 != 5
<=> 12 != 5Also wo liegt mein Denkfehler. Oder was hab ich an modularer Multiplikation nicht verstanden?
-
http://www.thi.informatik.uni-frankfurt.de/~jukna/Grundlagen/12woche.pdf
evtl. ist der abschnitt ueber kongruenzen hilfreich (?)
-
Hmm, also da dein Link von ner Uni kommt und ich mal davon ausgehe, dass das richtig ist, was da steht, muss bei mir irgendwo ein Denkfehler liegen.
In der PDF steht bei Kongruenz folgendes:Sei
x = y mod m und a = b mod m- x^d= y^d mod m
Gegenbeispiel: d=2 y=8 m=5 => 8^2 mod 5 = 64 mod 5 = 4 ; (8 mod 5)2=32=9
- x^d= y^d mod m
-
Das ist kein Gegenbeispiel, 4 und 9 sind (in Z_5) DASSELBE!
-
achso ich muss also diese ergebnisse immer noch in dem entsprechenden "Z" sehen.
ja dann stimmt es.
ok, dann sag ich mal dank schön für die hilfe
ciao Lord