Modulare Exponentiation < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:53 Mo 03.09.2012 | | Autor: | Jack159 |
Hallo,
Bei unserer Matheklausur sind keine Taschenrechner erlaubt. Und es wird mit eventuell irgendwo auch das Thema "modulare Exponentiation" (RSA-Algorithmus) vorkommen. Daher suche ich die schnellste/einfachste Methode, um solche Aufgaben per Hand ohne Taschenrechner lösen zu können.
Hier mal an einem Beispiel meine aktuelle Vorgehensweise:
Berechnet werden soll y:
[mm] y\equiv7^{23} [/mm] (mod 143)
Zunächst würde ich mir die ersten paar Potenzen von 7 ausrechnen (In [mm] \IZ_{143}):
[/mm]
[mm] 7^0=1
[/mm]
[mm] 7^1=7
[/mm]
[mm] 7^2=79
[/mm]
[mm] 7^3=343\equiv57
[/mm]
[mm] 7^4=399\equiv113
[/mm]
[mm] 7^5=791\equiv76
[/mm]
[mm] 7^6=532\equiv103
[/mm]
Dann würde ich versuchen möglichst geschickt mit meinen bisher ausgerechneten Potenzen auf 7^(23) zu kommen:
[mm] (7^6)^3*7^5=7^{23}
[/mm]
Danach noch das ganze ausrechnen:
[mm] (103)^3*76=1092727*76\equiv64*76=4864\equiv2
[/mm]
Geht das auch irgendwie kürzer/schneller? Wie gesagt, in der Klausur müsste ich alles per Hand berechnen.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:03 Mo 03.09.2012 | | Autor: | Teufel |
Hi!
Kennst du Square-and-Multiply/Binäre Exponentiation? Das ist ungefähr das, was du machen willst, aber noch einen Tick besser. :)
Hierbei quadrierst du immer nur und erzeugst damit Zweierpotenzen als Exponenten. In deinem Fall würdest du also [mm] 7^1, (7^1)^2=7^2, (7^2)^2=7^4, (7^4)^2=7^8 [/mm] und [mm] (7^8)^2=7^16 [/mm] berechnen. Daraus kannst du dir dann auch die 23 zusammenbauen (16+4+2+1).
Das klappt, weil sich eben jede Zahl als Summe von Zweierpotenzen schreiben lässt (Binärdarstellung).
|
|
|
| |
|
Hallo Jack,
square and multiply ist in der Tat gut, klappt nämlich immer.
Manchmal kann man aber auch mal sehen, ob die spezifische Aufgabe nicht noch etwas anderes hergibt:
> Bei unserer Matheklausur sind keine Taschenrechner erlaubt.
> Und es wird mit eventuell irgendwo auch das Thema "modulare
> Exponentiation" (RSA-Algorithmus) vorkommen. Daher suche
> ich die schnellste/einfachste Methode, um solche Aufgaben
> per Hand ohne Taschenrechner lösen zu können.
>
> Hier mal an einem Beispiel meine aktuelle Vorgehensweise:
>
> Berechnet werden soll y:
>
> [mm]y\equiv7^{23}[/mm] (mod 143)
>
> Zunächst würde ich mir die ersten paar Potenzen von 7
> ausrechnen (In [mm]\IZ_{143}):[/mm]
>
> [mm]7^0=1[/mm]
> [mm]7^1=7[/mm]
> [mm]7^2=79[/mm]
> [mm]7^3=343\equiv57[/mm]
> [mm]7^4=399\equiv113[/mm]
> [mm]7^5=791\equiv76[/mm]
> [mm]7^6=532\equiv103[/mm]
>
> Dann würde ich versuchen möglichst geschickt mit meinen
> bisher ausgerechneten Potenzen auf 7^(23) zu kommen:
>
> [mm](7^6)^3*7^5=7^{23}[/mm]
Ja, sowas. Da muss man manchmal ein bisschen kreativ sein. 
> Danach noch das ganze ausrechnen:
>
> [mm](103)^3*76=1092727*76\equiv64*76=4864\equiv2[/mm]
[mm] 7^{23}\mod{143}
[/mm]
Man könnte ausnutzen, dass 143=11*13 ist. Also [mm] 7^{23}\mod{11} [/mm] und [mm] \mod{13} [/mm] bestimmen und dann per chinesischem Restsatz wieder zurück, der geht hier so ziemlich im Kopf. Der erste Teil ist weniger fehleranfällig als Dein Weg (einfach weils kleinere Zahlen sind), dafür hat der zweite Teil Fallen.
Wir wissen [mm] 7^{10}\equiv 1\mod{11} [/mm] und vielleicht weißt Du auch [mm] 7^3=343 [/mm] auswendig, also [mm] 7^{23}\equiv 7^3\equiv 343\equiv 2\mod{11}.
[/mm]
Bei der 13 braucht man eine andere Überlegung. Es ist [mm] 7^{12}\equiv 1\mod{13}.
[/mm]
Also ist auch [mm] 7^{24}\equiv 1\mod{13}. [/mm] Hm, Mist. Exponent zu groß...
Hier brauchen wir das Inverse von [mm] 7\mod{13}. [/mm] Das ist schnell gefunden, nämlich die 2, also [mm] 7^{23}\equiv 7^{24}*2\equiv 2\mod{13}.
[/mm]
Und hier sieht man, dass der chin.RS gar keine Schwierigkeiten bereitet.
[mm] x\equiv 2\mod{11} [/mm] und [mm] x\equiv 2\mod{13} [/mm] heißt natürlich [mm] x\equiv 2\mod{143}.
[/mm]
> Geht das auch irgendwie kürzer/schneller? Wie gesagt, in
> der Klausur müsste ich alles per Hand berechnen.
Mein Weg hier klappt oft gar nicht gut, also genau hinschauen, was möglicherweise hilfreich wäre. Bei dieser Aufgabe wäre ich schneller gewesen als auf Deinem Weg oder mit "square and multiply", ausnahmsweise.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:41 Mo 03.09.2012 | | Autor: | Jack159 |
Hallo,
Danke für eure beiden Tipps.
Die Square & Multiply wirkt auf den ersten Blick einfacher, aber hier muss man letzendlich ja öfters multiplizieren als bei meiner Methode. Dafür hätte man es hier aber mit kleineren Zahlen zu tun....
Die Chinesische Restsatzmethode wirkt mir persöhnlich etwas zu aufwendig.
Zuviele Dinge auf die man aufpassen muss. Ein Risikio, dass ich in der Klausur nicht eingehen will.
Ich denke ich werde bei meiner Methode aus dem Startpost bleiben.
Ein Übersichtliches/einfaches Schema, bei dem (meiner Meinung nach) die einzige Hürde die etwas zu groß werdenen Zahlen werden könnten.
Trozdem danke für eure beiden Vorschläge ;)
|
|
|
|
