4. Modulo Problem

Modulo Problem

  • S

    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.

    0
  • B

    200^200 mod 256 = (((200*200 mod 256) * 200 mod 256) * 200 mod 256) * 200 mod 256 ... [200x]

    0
  • S

    Ah, denke ich hab's kapiert. Jedoch müsste es nicht ... [200x] sein, sondern ... [199x], oder?

    x^y mod z = ((x*x mod z) * x mod z) ... [y-1 *]

    0
  • T

    Etwas tollerer geht das so:

    z.b.: 200200=(200100)2=((20050)2)2=(((20025)2)2)2=((((200⋅(20012)2))2)2)2200^{200} = (200^{100})^2 = ((200^{50})^2)^2 = (((200^{25})^2)^2)^2 = ((((200\cdot(200^{12})^2))^2)^2)^2 =...= ... (jeweils mod 256)

    Viel weniger Rechenoperationen.

    0
  • J

    Und mod 256 rechnen geht prima, indem man das ganze einfach in ner 8Bit-Variable rechnet. Dann muß man dafür nichtmal was tun. 😃

    edit: wobei 200^200 mod 256 ziemlich langweilig ist. In der 200 stecken ja 2 2en. Durch das multiplizieren kommen immer mehr 2en rein (immer 2 dazu). Sobald 8 drin sind isses eh 0 mod 256.

    0
Anmelden zum Antworten