Hallo,

wie kann ich den Rest bei großen Exponenten bzw. Zahlen bestimmen, ohne dass ich beim Programmieren einen Überlauf erzeuge? Möchte z.B. den Rest von 200 hoch 200 (mod 256)? Wenn ich jedoch 200 hoch 200 rechne, so sprenge ich ja schon jede Variable und bekomme natürlich ein falsches Ergebnis. Zur Info: Ich will es in C# programmieren, aber wenn es einen Algorithmus gibt, ist es ja eigentlich egal, welche Sprache ich da nehme. Der kleine Satz von Fermat oder Satz von Euler scheint mir da noch nicht das richtige zu sein, oder sollte ich mich da täuschen?

Danke.

(edit fal: Topictitel)

Du kannst das ganze etwas zerlegen. Das modulare Exponieren hat nämlich einen Vorteil, man kann es in Stücken machen. Und das geht etwa so:

a^5 mod b = (a^2)^2 * a mod b = ((a^2 mod b)^2 mod b)*a mod b
so kannst du den Expoenenten lansam zerlegen, so dass du nur noch Quadrate und Multiplationen hast, nach jedem kleinen Schritt rechnest du Modulo, so dass deine Zahlen immer schön im Rahmen bleiben.