Wie löse ich hohe Potenzen ohne Taschenrechner

Neue Frage »

10.07.2005, 23:48	Maxwell	Auf diesen Beitrag antworten »
Wie löse ich hohe Potenzen ohne Taschenrechner Habe bald eine Klausur und erst gerade erfahren dass ich dort keinen Taschenrechner verwenden darf. Es soll dort mit Hilfe des RSA-Verfahrens verschlüsselt werden. Dabei ist zB in einer der alten Klausuren die Gleichung: $\begin{eqnarray} y \equiv 3^{133} \end{eqnarray}$ mod $\begin{eqnarray} 113 \end{eqnarray}$ zu lösen. Da muss es doch eine Möglichkeit geben durch irgendeine Regel die Potenz zu senken.
10.07.2005, 23:53	simonko_	Auf diesen Beitrag antworten »
also senken kannst du sie nicht. du kannst sie aber teilen z.b 2^12= (2^3)^4 diese potenzregel einfach anweden. sonst fällt mir auch niks ein
10.07.2005, 23:57	zoiX	Auf diesen Beitrag antworten »
Das Thema hatten wir hier erst kürzlich schonmal... Ohne Taschenrechner wußte da niemand einen Ausweg - den Link zum alten Thread geb ich dir aber gern: http://www.matheboard.de/thread.php?threadid=19257 Da sind zwei Wege zur Bestimmung des Divisionsrestes beschrieben - leider gehen beide davon aus, dass du einen TR benutzen darfst. Sicher das die Zahlen in der Klausur derart hoch werden? $\begin{eqnarray} 3^{133} = (3^7)^{19} \end{eqnarray}$ Weiter gehts nich - da wird die Sache nich viel einfacher durch, oder?
11.07.2005, 00:13	simonko_	Auf diesen Beitrag antworten »
mir ist noch was eingefallen. gegeben sei z^x du zerlegst z in (a+b) und wendest dann das paskalische dreieck an. damit ist es sehr leicht nur sehr zeitaufwendig
11.07.2005, 00:14	JochenX	Auf diesen Beitrag antworten »
was ist der witz an der aufgabe? was soll überhaupt gemacht werden alle y der form y=3^(133)+z*113 mit z aus Z erfüllen diese kongruenz hab ich was missverstanden? soll etwa (entsprechend dem anderen thread, da finde ich hier aber nix von) das kleinste natürliche y gefunden werden?
11.07.2005, 00:21	Maxwell	Auf diesen Beitrag antworten »
Jo bin mir leider sicher dass solche hohen Zahlen rankommen, da diese Aufgabe aus einer bereits geschriebenen Klausur stammt. Habe durch rumprobieren festestellt, dass $\begin{eqnarray} 3^{113} \end{eqnarray}$ mod $\begin{eqnarray} 113 = 0 \end{eqnarray}$ dies scheint nur zu funktionieren da 113 eine Primzahl ist. Warum das gilt habe ich leider noch nicht rausgefunden. Aber auch $\begin{eqnarray} 3^{21} \end{eqnarray}$ ist noch eine Recht komplexe Aufgabe ohne TR. Eine lange und Zeitaufwendige Lösung würde nicht helfen, für die Aufgabe gibt es 1/23 Punkten macht bei 90 Minuten Bearbeitungszeit ca 4 Minuten. Ich werde mal den alten Thread duchlesen, aber wenn es da mit TR gelöst wird hilft es wenig. Vielen Dank erstmal schreibt Bitte wenn euch noch was einfällt. edit: Es soll eine Lösung zwischen 0 und 112 gefunden werde, also daher der modulo am Ende muss aufgelöst werden. edit2: $\begin{eqnarray} 3^{113} \end{eqnarray}$ mod $\begin{eqnarray} 113 = 3 \end{eqnarray}$ sorry
Anzeige

11.07.2005, 00:41	dfg	Auf diesen Beitrag antworten »
Kommt dir das hier bekannt vor? $\begin{eqnarray} a^{p-1} \equiv 1 ~ (mod ~p) \end{eqnarray}$ für $\begin{eqnarray} ggT(a,p)=1 \end{eqnarray}$ Das ist der kleine Satz von Fermat, den kannst du hier wunderbar anwenden. Also ist $\begin{eqnarray} 3^{113} ~ (mod ~ 113) \end{eqnarray}$ doch $\begin{eqnarray} 0 \end{eqnarray}$ *g
11.07.2005, 00:48	Maxwell	Auf diesen Beitrag antworten »
Aso danke dfg, daher gilt dann auch die Beziehung ide ich oben zufällig gesehen habe. Also muss ich dann $\begin{eqnarray} 3^{21} \end{eqnarray}$ noch per Hand ausrechnen ? Oder ist der auch noch zu vereinfachen ?
11.07.2005, 00:59	dfg	Auf diesen Beitrag antworten »
Ach quatsch $\begin{eqnarray} 3^{113}~ (mod ~113) \end{eqnarray}$ ist doch 3 Man es ist schon spät xD Für den Rest musst du eine günstige Zerlegung finden z.B. $\begin{eqnarray} 3^{21} = (3^5)^43 = 17^43 \end{eqnarray}$ Günstig heisst also das bei Modulrechnung ein möglichst kleiner Rest rauskommt. um ein bisschen Handrechnung kommst du leider nicht herum *g
11.07.2005, 08:39	Denjell	Auf diesen Beitrag antworten »
man kann doch den modulo operator auch mehrmals zwischendurch anwenden, man berechnet z.b.: 3^5 mod 113=x (3^5) dann x*x mod 113 = z (3^10) usw. bis man sich 3^133 zusammengepuzzled hat.
11.07.2005, 11:46	AD	Auf diesen Beitrag antworten »
Fermat-Euler und andere Nettigkeiten mal außer acht lassend beträgt der Aufwand zur Berechnung von $\begin{eqnarray} a^n \mod m \end{eqnarray}$ etwa $\begin{eqnarray} O(\log_2(n)) \end{eqnarray}$ , wenn folgender Algorithmus zugrundegelegt wird: Man setze $\begin{eqnarray} a_0=a \end{eqnarray}$ sowie $\begin{eqnarray} a_k\equiv a_{k-1}^2\mod m \end{eqnarray}$ für k>0. Dann ist offenbar $\begin{eqnarray} a_k\equiv a^{2^k}\mod m \end{eqnarray}$ . Mit der Binärdarstellung des Exponenten $\begin{eqnarray} n=\sum\limits_k~b_k2^k \end{eqnarray}$ kann man dann die gewünschte Potenz $\begin{eqnarray} a^n \end{eqnarray}$ dann so bestimmen: $\begin{eqnarray} a^n\equiv \prod\limits_{k:\;b_k=1}~a_k\mod m \end{eqnarray}$ Unser Beispiel: $\begin{eqnarray} a=3 \end{eqnarray}$ , $\begin{eqnarray} m=113 \end{eqnarray}$ und $\begin{eqnarray} n=133=[10000101]_2=2^7+2^2+2^0 \end{eqnarray}$ . Wir benötigen die Potenzen $\begin{eqnarray} a_0 &=& 3^1 \equiv 3 \mod 113\\ a_1 &=& 3^2 \equiv 3^2 \equiv 9 \mod 113\\ a_2 &=& 3^4 \equiv 9^2 \equiv 81 \mod 113\\ a_3 &=& 3^8 \equiv 81^2 \equiv 7 \mod 113\\ a_4 &=& 3^{16} \equiv 7^2 \equiv 49 \mod 113\\ a_5 &=& 3^{32} \equiv 49^2 \equiv 28 \mod 113\\ a_6 &=& 3^{64} \equiv 28^2 \equiv 106 \mod 113\\ a_7 &=& 3^{128} \equiv 106^2 \equiv 49 \mod 113 \end{eqnarray}$ Dann ist $\begin{eqnarray} 3^{133}\equiv a_0a_2a_7\equiv 3\cdot 81\cdot 49\equiv 42\mod 113 \end{eqnarray}$ . EDIT: Schreibfehler korrigiert.

Neue Frage »

Antworten »

Wie löse ich hohe Potenzen ohne Taschenrechner

Verwandte Themen