Modulo große Exponenten?
Hi, also ich will z.B [2]^23 mod 16 berechnen. Ich hatte es mir so überlegt:
(= -> Äquivalenz ) 3^23 = 3^22 * 3 = (3^11)^2 * 3 = [1]*[3]=4 mod 16,
laut Wolfram alpha ist das Ergebnis 11 mod 16.
Was hab ich falsch gemacht?
grüß
Was willst du berechnen, 2^ oder 3^?
Ich nehme mal an 3^, sonst wäre das ja auf jeden Fall 0.
ja 3^seh grade ich hab aufjedenfall einen Rechenfehler bei 3^11
1 Antwort
Also, falls du 3^23 meinst: Zunächst einmal kann dein Ergebnis nicht richtig sein, 3^23 ungerade ist und du modulo einer geraden Zahl nimmst. Und das kann nur ein ungerades Ergebnis sein, denn letztlich bedeutet modulo ja, dass man (manchmal sehr oft) die Zahl abzieht. Und ungerade - gerade bleibt ungerade.
Ich würde 3^4 = 81 benutzen, denn dann siehst du
3^4 mod 16 = 81 mod 16 = 1.
3^23 = 3^20 * 3^3 = (3^4)^5 * 3³
Und das modulo:
(3^4)^5 * 3³ modulo 16 = 1^5 * 27 modulo 16 = 27 modulo 16 = 11.
Genau, man kann das modulo rechnen ja in die Operationen hineinziehen.
Also etwas verkürzt geschrieben (a*b) mod x = a mod x * b mod x.
Und dann eben die richtigen Stückelungen finden. Dazu hilft es, so ein paar Potenzen im Kopf zu haben, 2er und 3er sind da sehr nützlich.
Alles klar, super. Habs jetzt endlich mal richtig verstanden. Danke!
ja genau, deswegen kann es nicht stimmen. Wie berechne ich hier das Modulo geschickt? Also es geht mir vor allem um große Exponenten.
Der "Trick" dabei ist, sich einen Potenzwert auszusuchen, den man sinnvoll modulo nehmen kann.
ok, also einfach versuchen die Exponenten geschickt in kleiner "Teile" zu zerstückeln . Danke hat mir geholfen.