A^b mod x, wobei b eine große zahl ist, tips?

Wissenschaft Mathematik
#1

Hallo liebe Leute.

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?

Gruß

#2

Hallo,
der Algorithmus heißt square and multiply und basiert auf der Binärdarstellung des Exponenten, siehe Wikipedia: Binäre Exponentiation.

Grüße, guidot

#3

Hossa :smile:

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).

Viele Grüße

Hasenfuß

#4

Hi,

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.

Ciao Lutz