13^{11223322} mod 22 |
| 23.01.2011, 16:02 | japr0 | Auf diesen Beitrag antworten » |
| 13^{11223322} mod 22 Hi, ich stehe hier vor der Aufgabe, dass ich 13^{11223322} mod 22 'möglichst elegant' bestimmen soll. Normalerweise haben wir das in der VL immer mit dem 'Square and Multiply' Algorithmus gemacht. Das Problem ist, dass ich mit 11223322 schon eine extrem große Binärzahl bekomme und wenn ich nun einen 3-Seitigen SaM Algorithmus anwende, ist das bestimmt nicht 'möglicht elegant'... Gibt es bei der Aufgabe einen Trick, den ich einfach gerade nicht sehe ? Meine Ideen: WolframAlpha gibt mir als Ergebnis 15, was mich darüber hinaus ein wenig verunsichert, weil wir bisher bei 'so großen Exponenten', immer als Ergebnis 0 bekommen haben. Dies konnte man dann meist nach 2 -3 Iterationen erkennen und war dann bereits fertig. Irgendwie kann es ja nicht Sinn der Aufgabe sein 3 Seiten lang einen Algorithmus durchzuspielen ? Danke |
||
| 23.01.2011, 16:07 | jester. | Auf diesen Beitrag antworten » |
Benutze den Satz von Euler-Fermat: http://de.wikipedia.org/wiki/Satz_von_Euler |
||
| 23.01.2011, 17:39 | japr0 | Auf diesen Beitrag antworten » |
super, damit war es ganz leicht! Vielen Dank. |
||
|
|