Modulo aus großen zahlen einfacher

ralph0815

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.

fubar

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.

Jester

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

WebFritzi

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
= 1

Dabei 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).

fubar

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"

Jester

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 = a^p+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

Jester

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.

Termite

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 = 16087

Für jede 1 in der bnärdarstellung wird gerechnet X = X^2 * n
Für jede 0 : X = X^2

Angefangen 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 m

gruss Michael Graf

WebFritzi

@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.

Jester

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=0^p (p über k) * a^k*b^p-k

Soweit 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

WebFritzi

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".