Habe mich etwas mit modulo Rechnungen beschäftigt. Gerade entdeckt, dass man sich vieles leichter machen kann. Wenn wir zum Beispiel a^8 mod x hätten, dann müsste man nicht (a*a*a*…) mod x machen sondern geht leichter indem man ((a^2 mod n)^2 mod n)^2 mod n macht
Das ist jetzt auch klasse. Aber was mache ich wenn ich eine wirklich sehr große Zahl habe? Sagen wir a^8573 mod x?
Das ist so enorm, da wüsste ich garnicht wie ich anfangen soll. Also bei der ersten Aufgabe mit der Zahl a^8 sehe ich irgendwie schnell dass ich das in drei Teile aufteilen kann (weil 2*2*2 = 8 ). Aber bei a^8573 zum Beipsiel, pf… ne. Wie würde man bei so eine Aufgabe rangehen? Was wäre schön und einfach?
Gegeben: a (zu potenzierende Zahl), e (Exponent) und m (Modul)
Gesucht: r= (a^e) mod m
1: function aHOCHeMODm( a, e, m )
2: r= 1; //Zum Aufbau des Ergebnisses
3: while (e\>0)
4: { if (e&1) r= (r\*a)%m; //Nur wenn rechtestes Bit von e gesetzt
5: a= (a\*a)%m; //Exponent von a verdoppeln
6: e\>\>=1; //Schiebe alle Bits um 1 nach rechts
7: }
8: return r;
Die Bedingung e&1 in Zeile 4 prüft, ob das rechteste Bit gesetzt ist, ob also e ungerade ist.
In Zeile 5 wird a mit sich selbst multipliziert, was einer Verdopplung des aktuellen Exponenten entspricht.
Alternativ kann Zeile 6 auch durch eine Division durch 2 ersetzt werden, also e=e/2 (für Programmiersprachen, die keine Bits schieben können).
wenn Du x in Primfaktoren faktorisieren kannst und a und x teilerfremd sind, dann kannst Du die Eulersche-Phi-Funktion von x bestimmen und dann benutzen, dass
a^phi(x)==1 (mod x)
gilt, d.h. in Anwendung
a^b==a^(b mod phi(x)) (mod x),
wobei mod als Operation die Restbestimmung bei Ganzzahldivision ist.
