schnelle exponentation < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:34 Mo 02.03.2009 | | Autor: | lula |
Hallo zusammen,
kann mir jemand die schnelle Exponentation erklären?
Warum ist z.B. [mm] 7^{273}=((49 [/mm] mod 9)*7) mod 9 =1 und
[mm] 7^{68}= [/mm] 16 mod 9 ?
Wäre toll, wenn mir das jemand etwas genauer erläutern könnte....
LG, Lula
|
|
| |
|
Hallo lula,
wo hast Du denn diese Rechnungen her?
Das, was Du "schnelle Exponentiation" nennst, geht z.B. wie folgt:
gesucht [mm] 7^{273}\mod{9}
[/mm]
Nun ist 273=3*7*13
Außerdem ist [mm] 7^3\equiv(-2)^3 \equiv 1\mod{9}
[/mm]
Wie praktisch... Denn nun kann man so rechnen:
[mm] 7^{273}=(7^3)^{91}\equiv 1^{91}=1 \mod{9}
[/mm]
und [mm] 7^{68}=7^{66}*7^2=(7^3)^{22}*7^2\equiv 1^{22}*7^2=49\equiv 4\mod{9}
[/mm]
Vielleicht konnte ich darum Deine zweite Rechnung nicht nachvollziehen...
Die erste übrigens auch nicht. Aber ein ähnlicher Weg wie oben dürfte es gewesen sein.
Grüße reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:15 Mo 02.03.2009 | | Autor: | lula |
Ok, vielen Dank, das hat mir auf jeden Fall schon mal weiter geholfen. Die von mir angegebene Rechnung habe ich aus einem Buch, ist etwas anders als dein Weg. Hier dieser nochmal ausführlich:
[mm] 7^{273}mod [/mm] 9
[mm] 7^{273}=(7^{136})^{2}*7=((49mod [/mm] 9)*7)mod 9=1
[mm] 7^{136}= (7^{68})^{2}=16 [/mm] mod 9 =7
[mm] 7^{68}=(7^{34})^{2}=49 [/mm] mod 9 = 4
usw.
[mm] 7^{2}=7*7=49 [/mm] mod 9 =4
Vielleicht wird das so verständlicher und ihr könnt mir das noch etwas erläutern....
Viele Grüße, Lula
|
|
|
| |
|
Hallo lula,
ah, das hilft in der Tat, den Rechengang nachzuvollziehen.
Allerdings gibt das Buch die Rechnung eigenartig wieder, denn eigentlich schreibt man erst einmal von oben nach unten:
[mm] 7^{273}=\blue{7^{(2*136+1)}}=\left(7^{136}\right)^2*7=\ [/mm] ?
[mm] 7^{136}=\blue{7^{(2*68+0)}}=\left(7^{68}\right)^2=\ [/mm] ?
[mm] 7^{68}=\blue{7^{(2*34+0)}}=\left(7^{34}\right)^2=\ [/mm] ?
[mm] 7^{34}=\blue{7^{(2*17+0)}}=\left(7^{17}\right)^2=\ [/mm] ?
[mm] 7^{17}=\blue{7^{(2*8+1)}}=\left(7^{8}\right)^2*7=\ [/mm] ?
[mm] 7^{8}=\blue{7^{(2*4+0)}}=\left(7^{4}\right)^2=\ [/mm] ?
[mm] 7^{4}=\blue{7^{(2*2+0)}}=\left(7^{2}\right)^2=\ [/mm] ?
[mm] 7^{2}=\blue{7^{(2*1+0)}}=\left(7^1\right)^2=\ [/mm] ?
[mm] 7^{1}=\blue{7^{(2*0+1)}}=\left(7^0\right)^2*7=\ [/mm] ?
Das ist nichts weiter als der ![[]](/images/popup.gif) Euklidische Algorithmus, auf (273;2) angewandt. Man könnte auch sagen, der Exponent wird erst einmal in eine Binärzahl umgewandelt, nämlich [mm] 100010001_2.
[/mm]
Nun können wir in umgekehrter Reihenfolge ("von unten nach oben") vorgehen und haben in jedem Schritt höchstens zu quadrieren, mit 7 zu multiplizieren und wieder den Rest [mm] \mod{9} [/mm] zu bestimmen. Alles einfache Operationen, und die größte zu berechnende Zahl ist [mm] 8^2*7=448\equiv 7\mod{9}. [/mm] Das kann man ja sogar noch im Kopf rechnen.
Dies ist sozusagen die brute-force-Methode, funktioniert aber immer. Man hält gar nicht erst Ausschau nach eleganten Vereinfachungen, sondern rechnet stur und methodisch drauflos.
Für die Darstellung ist aber wesentlich, dass man erst ("von oben nach unten") den euklidischen Algorithmus bis zum Ende durchläuft und erst dann vom Ende aus ("von unten nach oben") die Restklassen bestimmt.
Probiers doch mal mit einer anderen, kürzeren Aufgabe aus:
[mm] 5^{111}\mod{13}\equiv\ [/mm] ?
Grüße
reverend
|
|
|
| |
|
Hallo lula,
ich kann reverends Rechnungen nur bestätigen und möchte nur darauf hinweisen, dass du alternativ auch den kleinen Satz von Fermat heranziehen kannst.
$7$ und $9$ sind ja wunderbar teilerfremd, damit auch [mm] $7^k$ [/mm] und $9$
Mit [mm] $\varphi(9)=\varphi(3^2)=3^2\cdot{}\left(1-\frac{1}{3}\right)=6$ [/mm] kannst du ganz ähnlich reverends Zerlegung arbeiten und dir zunutze machen, dass [mm] $\left(7^k\right)^{\varphi(9)}\equiv [/mm] 1 \ [mm] \mod [/mm] 9$ ist
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:30 Di 03.03.2009 | | Autor: | lula |
Super, dass ich von unten nach oben rechnen muss, war der entscheidende Hinweis. Das mit dem Fermat muss ich mir nochmal in Ruhe genauer anschauen, hab ich jetzt so noch nicht verstanden...
Vielen Dank für eure Hilfe!
LG, Lula
|
|
|
|
