[gelöst] Schnelle Exponentiation

[freakC++]

Hallo zusammen,

ich benutze momentan die binäre Exponentiation zum Berechnen des folgenden Terms:

338^{283} \mod 713

Hier ist der Algorithmus: http://de.wikipedia.org/wiki/Binäre_Exponentiation

Bis jetzt hat es immer perfekt funktioniert, doch irgendwie hat sich ein Fehler bei mir eingeschlichen und ich komme einfach nicht auf das richtige Ergebnis.

1.) Exponent in eine Binärzahl umwandeln: 283 == 100011011
2.) Jede 1 wird zu QM und jede 0 zu M (Q == quadrieren, M == multiplizieren). Dabei kann die führende 1 durch x ersetzt werden, da 1^2 * x = x:

100011011 == M M M QM QM M QM QM == $((((x \cdot x \cdot x \cdot x)^2 \cdot x)^2 \cdot x \cdot x)^2 \cdot x)^2 \cdot x$

Dabei muss nach jedem Rechenschritt "mod 713" gerechnet werden. Das richtige Ergebnis lautet 472, doch komme ich auf 671, das mir auch wolframalpha bestätigt:

[url]
http://www.wolframalpha.com/input/?i=(((((338++338++338++338%29^2+*+338%292++338++338%29^2+*+338%29+2++338%29+mod+713[/url]

Also gehe ich davon aus, dass meine Formel nicht stimmt, doch den Fehler sehe ich leider nicht. Könnt ihr mir helfen?

Vielen Dank
LG, freakC++

[freakC++]

Ich Trottel!! 0 muss durch Q ersetzt werden und nicht durch M.

[knivil]

Fix und fertig: http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method