Modulo aus großen zahlen einfacher
-
Hallo. Ich will aus sehr großen zahlen den modulo ziehen, doch das is mit meiner programmiersprachen("java") nicht so einfach. ich habe informatik in der schule und soll jetzt das rsa-verfahren programmieren. doch da gibt es sehr große zahlen. ich darf keine biginteger oder sontiges nehmen nur long. aber jetzt kommt der wichtige punkt. wenn ich die aufgabe habe 12^32modulo5, dann hat mein teacher gesagt, dass man die rechnung zerlegen kann. ich habe jetzt schon solange nachgedacht, dass ich meinen kopf dabei zerlegt habe, aber trotzdem keine kösung habe. ich hoffe hier gibt es einen profi der sich damit auskennt.
-
Hallo,
modulo ist ein sogenannter Homomorphismus, das heißt er verträgt sich mit der Struktur von Addition und Multiplikation, in Formeln:
Sei Phi(x) = x mod a, a feste Zahl.
Dann ist Phi(x*y) = Phi(x)*Phi(y) (Achtung: anderer Malpunkt, hier Z/aZ)
Phi(x+y)=Phi(x)+Phi(y) (auch hier, das + ist in Z/aZ)Das bedeutet für Dein Beispiel:
12^32 mod 5 = (12 mod 5)^32 = 2^32 (allerdings in Z/5Z, das heißt Du darfst weiterhin alle Rechnungen modulo 5 durchführen). Außerdem weiß man aus der Gruppentheorie, daß in Z/aZ x^(a-1) = 1 ist, falls x!=0. Also ist 2^4=1.
Damit genügt 2^(32 mod 4) zu berechnen, also 2^0=1.
Damit ist das Ergebnis Deines Beispiels 1.Also kleine Anleitung: erst modulo innenrein ziehen. Anschließend den Exponenten noch modulo eins weniger, danach berechnen. Das sollte schonmal einiges bringen.
MfG Jester
P.S.: Genaueres solltest Du in jedem Algebra-Buch finden.
-
In Maple könnte das so aussehen:
mod_pot:=proc(c::integer,y::posint,n::posint)local b,x,z; b:=c; x:=y; z:=1; b:=b mod n; while(x<>0) do if x mod 2 =0 then b:=b^2 mod n; x:=x/2; else x:=x-1;z:=(z*b) mod n; fi; od; z; end proc;Begründung:
Das modulare potenzieren x^c mod n kann in c-1 modulo-Multiplikationen geschehen, ist aber sehr ineffizient, wenn c groß ist.
Der "square-and-multiply"-Algorithmus reduziert die Anzahl der modulo-Multiplikationen auf höchstens 2*m, wobei m die Anzahl der Bits der Binärdarstellung von c ist. Da m<= k, kann x^c mod n in O(k^3) berechnet werden.
-
könnte jester mir nochmal die zeile:12^32 mod 5 = (12 mod 5)^32 = 2^32 (allerdings in Z/5Z, das heißt Du darfst weiterhin alle Rechnungen modulo 5 durchführen. näher erklären. ich habe nichts verstanden und das mit mapple is mir auch unklar.
-
ralph0815 schrieb:
... und das mit mapple is mir auch unklar.
Wenn du das ganze programmieren sollst, schau dir doch den Algorithmus in Maple-Syntax an und versuche, das so in Java umzusetzen! Ist eigentlich gar nicht schwer...
:=
=
mod %
<> !=
usw.
-
12^32 mod 5, das mit dem mod 5 hatten wir vorhin mal geschrieben, als Phi(...), erinnerst Du Dich? Das benutzen wir jetzt nochmal:
Phi(12^32) = Phi(12*12*...*12)
und mit der Regel, daß Phi(x*y) = Phi(x)*Phi(y) ist erhalten wir:
=Phi(12)*Phi(12)*...*Phi(12)Phi(12) = 12 mod 5= 2, also:
=2*2*...*2 = 2^32 und Z/5Z bedeutet einfach: normales Rechnen, aber immer alles modulo 5 nehmen. Dann den Trick anwenden mit x^a-1. Anschließend solltest Du zum fertig potenzieren noch den von fubar angesprochenen Algorithmus verwenden. Das drückt von O(n) auf O(log n).Ich hoffe, das ist etwas klarer geworden. Ansonsten würde ich Dir wirklich einen kleinen Blick in ein Buch über Gruppen und Ringtheorie empfehlen.
MfG Jester
-
Lieber Jester!
Anstatt dich so kompliziert auszudrücken, sag doch lieber, dass 12^32 mod 5 das gleiche ist wie((12 mod 5)^32) mod 5 = 2^32 mod 5 = ((2^4)^8) mod 5 = ((2^4 mod 5)^8) mod 5 = 1^8 mod 5 = 1 mod 5 = 1Dabei wurden die folgenden Regeln angewandt:
(a) a^b mod m == ((a mod m)^b) mod m (b) a^(m-1) mod m = 1, wenn a kein ganzzahliges Vielfaches von m ist.Dabei hab ich jetzt nur deinen Text "übersetzt". Ich fänd's geil, wenn du mir diese beiden Regeln mal beweisen könntest - vor allem (b).
-
WebFritzi schrieb:
Ich fänd's geil, wenn du mir diese beiden Regeln mal beweisen könntest - vor allem (b).
b) ist IMHO "Der kleine Satz von Fermat"
-
Was soll ich denn an den Regeln groß beweisen? Daß modulo ein Homomorphismus ist weißt Du selbst, oder? Damit folgt schon, daß ich das mod in die Potenz reinziehen kann.
Nein, der Fermat sagt was über Gruppen aus. Ich habe einen Satz über Körper benutzt:
In Z/pZ gilt:
(a+b)^p = a^p + b^p, denn p teilt alle andere Binomialkoeffizienten (p über k) mit k!=0 und k!=p.E ist sicher 0^p = 0, 1^p = 1.
Sei jetzt also a^p=a, dann ist wegen (a+1)^p = ap+1p = a+1 (IV) ebenfalls gleich (alles mod p zu lesen). => Induktion, gilt für alle Elemente diese Körpers.Also a^p = a mod p für alle a. Ist jetzt a!=0, so kann ich mit a^-1 multiplizieren und erhalte:
a^p-1 = 1 mod p.MfG Jester
-
Ich finde WebFritzi sollt grundsätzlich alles überestzen was Jester so von sich gibt
-
Weißt Du, ich denke das hat zwei Gründe:
- Nicht alle Mathematik läßt sich auf dem Niveau einer Grundschule abhandeln
- Ich versuche für gewöhnlich noch zu begründen, warum meine Rechnung korrekt ist. Wenn Dir das zu viel ist und Du einfach nur wissen willst wie "man's rechnet", dann laß die Erklärungen weg und Du hast eine Kette von Gleichheitszeichen bis zum Ende.
So, Webfritzi, könntest Du ihm das bitte übersetzen?
MfG Jester
-
sry, so war das ja gar nicht gemeint. Ich finds sehr gut, dass du alles begründest und Hintergrudinformation gibts, anstatt einfach das Ergebnis/ die Formel hinzu klatschen.
WebFritzi hatte halt so eine erfrischende einfache Art dein Gesagtes noch mal zusammen zu fassen
Es war also gar nich so furchtbar Ernst gemeint.
-
Hi
zu diesem thema gibts nen alg. wie der genau ausseht kann ich nicht mehr rekonstruieren.
Beispiel 7^5 = 16807
Die 5 wird binär dargestellt = 101
gerechnet wird nun folgendes
1^2 * 7 = 7
7^2 = 49
49^2 * 7 = 16087Für jede 1 in der bnärdarstellung wird gerechnet X = X^2 * n
Für jede 0 : X = X^2Angefangen mit dem höchstwertigen bit. x wird am anfang auf 1 gesetzt.
das ganze lässt sich natürlich auch mit den oben gananten modulo regeln erweitern
Für jede 1 : X = ( ( ( X * X ) mod m ) * n ) nod m
für jede 0 : X = ( ( X * X ) mod mgruss Michael Graf
-
@Jester: Mir ist einiges nicht klar, was du schreibst. Z.B.:
In Z/pZ gilt:
(a+b)^p = a^p + b^p, denn p teilt alle andere Binomialkoeffizienten (p über k) mit k!=0 und k!=p.Das verstehe ich nicht. Ich muss zugeben, dass ich nicht das As in Algebra bin. Ich konnte z.B. keine einzige Aufgabe auf dem zweiten Zettel in Algebra I lösen. Ich bin eher der analytische Typ. Ich denke auch, dass wir uns deswegen hier im Forum perfekt ergänzen. Bitte gehe nicht davon aus, dass das, was du bisher geschrieben hast, einfach zu verstehen ist. Ich stelle mich da auf die selbe Stufe wie ein Schüler in der Oberstufe. Ich kapier sowas nicht so schnell.
-
Jo, ich werd mich benühen.
Rechnen in Ringen wie diesen, das ist wie ganz neu rechnen lernen, aber wenn man's mal gefressen hat, dann isses genauso einfach wie normales rechnen.Okay, also zu dieser fraglichen Zeile:
in Z/pZ ist ja alles 0, was vielfaches von p ist.
(a+b)^p = Σk=0p (p über k) * ak*bp-kSoweit stimmen wir denke ich vollkommen überein.
Meine Behauptung ist jetzt: p teilt (p über k) für k!=0 und k!=p, das heißt: in der Summe bleiben nur die beiden Randfälle a^p, b^p stehen. Der Rest ist 0, weil vielfaches von p. (Ich glaub da hab ich oben mehrmals mit nem n statt p danabengehauen.)
Wenn wir uns das nämlich mal anschaun:
(p über k) = p!/(k!(p-k)!) und sobald k nicht 0 oder p ist steckt im Nenner kein p drin. Damit kann es im Zähler aber auch nicht gekürzt werden, da es ja prim ist. Also teilt p den Binomialkoeffizienten.Ich hoffe, das ist jetzt klar(er) geworden.
MfG Jester
-
Danke für die Erklärung. Ist super. Jetzt hab auch ich's verstanden. Nur bitte ich dich, einen Fehler zu korrigieren (zu edititeren), wenn du ihn gefunden hast. Das ist einfach besser als zu schreiben "Oh, oben habe ich glaub ich einen Fehler gemacht".