Rechnen mit sehr großen Zahlen

31.12.2014, 10:32	EverDare	Auf diesen Beitrag antworten »
Rechnen mit sehr großen Zahlen Hi zusammen, ich sitze gerade über diversen Aufgaben meiner Kryptographie-Vorlesung und komme leider nicht weiter. Es handelt sich um Aufgaben der folgenden Machart: Zeigen Sie, dass $\begin{eqnarray} 2012^{2012} + 1 \end{eqnarray}$ durch 41 teilbar ist. Meine Idee ist, dass ich die folgende Kongruenz zeigen muss: $\begin{eqnarray} 2012^{2012}+1 \equiv 0 \; mod \; 41 \end{eqnarray}$ . Das Problem ist ja jetzt, dass ich den riesigen ersten Term so weit runterbrechen muss (vermutlich mithilfe von Kongruenzen?), um die Teilbarkeit direkt zu sehen. Ich denke, $\begin{eqnarray} 2012^{2012} \end{eqnarray}$ muss ich also so umformulieren, dass am Ende $\begin{eqnarray} 2012^{2012} \equiv -1 \; \end{eqnarray}$ rauskommt. Aber wie mache ich das? Basis und Exponent separat runterbrechen? Unter welchem Stichwort kann ich denn nach solchen und ähnlichen Aufgaben suchen? Das ist gerade mein Hauptproblem. LG und danke im Voraus, Ever
31.12.2014, 11:12	URL	Auf diesen Beitrag antworten »
RE: Rechnen mit sehr großen Zahlen Man will zeigen, dass $\begin{eqnarray} 2012^{2012} \equiv -1 \; mod \; 41 \end{eqnarray}$ ist. Basis und Exponent handlich machen ist eine gute Idee. Was den Exponenten angeht ist der kleine Satz von Fermat unverzichtbar. In seiner einfachsten - und hier verwendbaren - Form besagt er: Ist $\begin{eqnarray} p \end{eqnarray}$ eine Primzahl und $\begin{eqnarray} p \end{eqnarray}$ kein Teiler von $\begin{eqnarray} a \end{eqnarray}$ , dann ist $\begin{eqnarray} a^{p-1}\equiv 1 \bmod p \end{eqnarray}$ Hier also $\begin{eqnarray} 2012^{40}\equiv 1 \bmod 41 \end{eqnarray}$ . Deswegen schreibt man den Exponenten als $\begin{eqnarray} 2012=a40+b \end{eqnarray}$ . Bei der Basis ähnlich: $\begin{eqnarray} 2012^m=(r41+k)^m \equiv k^m \bmod 41 \end{eqnarray}$ . Das kann man sich leicht mit dem binomischen Lehrsatz überlegen. Wenn du Exponent und Basis so behandelst kommst du auf $\begin{eqnarray} 2012^{2012}\equiv 3^{12} \bmod 41 \end{eqnarray}$
31.12.2014, 14:13	EverDare	Auf diesen Beitrag antworten »
Hallo URL, danke für deine Antwort. Stimmt, den kleinen Satz von Fermat habe ich vergessen zu erwähnen. Ich kann deinen Ausführungen folgen bis $\begin{eqnarray} 2012^{40} \equiv 1 \; mod \; 41 \end{eqnarray}$ . Danach, ab "deswegen" (weswegen?), verstehe ich deine weiteren Schritte leider nicht mehr... . Dein Ergebnis, $\begin{eqnarray} 2012^{2012} \equiv 3^{12} \; mod \; 41 \end{eqnarray}$ , erhalte ich aber auf einem anderen Weg. In der Vorlesung haben wir das an einem kleinen Beispiel so gemacht: 1) Reduktion der Basis mod 41: $\begin{eqnarray} 2012 \equiv 3 \; mod \; 41 \end{eqnarray}$ 2) Reduktion des Exponenten mod 40: $\begin{eqnarray} 2012 \equiv 12 \; mod \; 40 \end{eqnarray}$ ==> insgesamt: $\begin{eqnarray} 2012^{2012} \equiv 3^{12} \; mod \; 41 \end{eqnarray}$ . Die $\begin{eqnarray} 3^{12} \end{eqnarray}$ hätte ich nun noch vereinfacht zu: $\begin{eqnarray} 3^{12} \equiv (3^2)^6 \equiv (9^2)^3 \equiv (-1)^3 \equiv -1 \; mod \; 41 \end{eqnarray}$ , also insgesamt: $\begin{eqnarray} 2012^{2012} \equiv 3^{12} \equiv (3^2)^6 \equiv (9^2)^3 \equiv (-1)^3 \equiv -1 \; mod \; 41 \end{eqnarray}$ Das stimmt doch so, oder? Wir haben in der Vorlesung zwei kleine Beispiele gerechnet (Umfang wie die o.g. Aufgabe), allerdings bei jedem ein anderes Vorgehen gewählt und ich weiß nicht, wann ich welches anwenden darf und warum bzw. warum und wann welches nicht. Beispielsweise haben wir den Beweis von $\begin{eqnarray} 2007^{2007} + 1 \end{eqnarray}$ ist durch 38 teilbar so gerechnet: 1) Reduktion der Basis mod 38: $\begin{eqnarray} 2007 \equiv 31 \; mod \; 38 \qquad \rightarrow \phi(38) = 18 \end{eqnarray}$ 2) Reduktion des Exponenten mod 18: $\begin{eqnarray} 2007 \equiv 9 \; mod \; 18 \end{eqnarray}$ ==> insgesamt: $\begin{eqnarray} 2007^{2007} \equiv 31^{9} \equiv -1 \; mod \; 38 \end{eqnarray}$ . Warum kommt hier plötzlich die Eulersche Phi-Funktion mit rein und im 2012er-Beipsiel nicht? Weil mein Modul hier keine Primzahl ist? Und dann reduziere ich den Exponenten immer um dieses $\begin{eqnarray} \phi \end{eqnarray}$ ? Würde ich den Exponenten als erstes reduzieren, müsste ich dann bei der Reduktion der Basis auch das entsprechende $\begin{eqnarray} \phi \end{eqnarray}$ als Modu verwenden? LG, Ever
31.12.2014, 14:36	URL	Auf diesen Beitrag antworten »
Was du bei diesem Beispiel gemacht hast, ist vollkommen richtig. Ich wusste nicht, wie viel Vorkenntnisse du mitbringst, deshalb sollten meine Bemerkungen das weitere Vorgehen motivieren. Z.B. für den Exponenten: Wegen $\begin{eqnarray} 2012^{40}\equiv 1 \bmod 41 \end{eqnarray}$ schreibt man den Exponenten als $\begin{eqnarray} 2012=a40+b \end{eqnarray}$ und bekommt $\begin{eqnarray} 2012^{2012}=2012^{a40+b}=(2012^{40})^a2012^b\equiv 2012^b \bmod 41 \end{eqnarray}$ Im konkreten Fall ist $\begin{eqnarray} 2012=50\cdot 40+12 \end{eqnarray}$ und das ist genau die Reduktion, die du auch bekommen hast. Für eine Primzahl $\begin{eqnarray} p \end{eqnarray}$ ist $\begin{eqnarray} \varphi(p)=p-1 \end{eqnarray}$ . Du hast also auch in diesem Beispiel die Eulersche Phi-Funktion benutzt. Schau dir die allgemeine Formulierung des kleinen Fermat an, da taucht sie auf. Reduktion des Exponenten verwendet den kleinen Fermat, deshalb $\begin{eqnarray} \bmod \varphi(n) \end{eqnarray}$ , Reduktion der Basis immer $\begin{eqnarray} \bmod\, n \end{eqnarray}$ . Warum das bei der Basis funktioniert, kannst du dir wie vorgeschlagen mit dem binomischen Lehrsatz überlegen.
31.12.2014, 15:32	EverDare	Auf diesen Beitrag antworten »
Aaaaaaah, vielen Dank, jetzt geht mir so manches Licht auf was die Reduktion angeht und die Phi-Funktion. Deine weiteren Bemerkungen werde ich mir in aller Ruhe zu Gemüte führen und versuchen, sie auch auf meine Aufschriebe bzw mein Skript anzuwenden. Vielen Dank für deine Mühen und guten Rutsch, Ever
31.12.2014, 15:38	URL	Auf diesen Beitrag antworten »
Gern geschehen. Viel Erfolg und unfallfreien Übergang ins neue Jahr
Anzeige

1

Verwandte Themen