RSA-Verfahren < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:29 Do 17.01.2008 | | Autor: | Lee1601 |
| Aufgabe | 108^13 mod 119
Exponent in 2er Potenzen zerlegen: [mm] 13=2^3+2^2+2^0
[/mm]
[mm] 108^{13}=108^{2^3}*108^{2^2}*108
[/mm]
108^(13) [mm] \equiv [/mm] 10 mod. 119 |
hey!
ich verstehe nicht, wie man oben rechnet....es ist klar, dass die zahlen zu groß für den taschenrechner sind...aber warum zerlegt man den exponenten in zweierpotenzen und noch viel wichtiger: wie kommt man letztlich zu dem ergebnis?
ist ein beispiel aus der vorlesung und auf dem rechenzettel haben ein ähnliches...verstehe die rechnung aber nicht :-(
hoffe mir kann jemand auf die sprünge helfen!
lg lee
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:37 Do 17.01.2008 | | Autor: | koepper |
Hallo Lee,
> 108^13 mod 119
> Exponent in 2er Potenzen zerlegen: [mm]13=2^3+2^2+2^0[/mm]
> [mm]108^{13}=108^{2^3}*108^{2^2}*108[/mm]
>
> 108^(13) [mm]\equiv[/mm] 10 mod. 119
> hey!
>
> ich verstehe nicht, wie man oben rechnet....es ist klar,
> dass die zahlen zu groß für den taschenrechner sind...aber
> warum zerlegt man den exponenten in zweierpotenzen und noch
> viel wichtiger: wie kommt man letztlich zu dem ergebnis?
> ist ein beispiel aus der vorlesung und auf dem
> rechenzettel haben ein ähnliches...verstehe die rechnung
> aber nicht :-(
> hoffe mir kann jemand auf die sprünge helfen!
mach mal eine Tabelle auf folgende Weise:
Du quadrierst 108, dann mod 119, dann nochmal quadrieren und wieder mod 119, dann nochmal usw...
Auf diese Weise bekommst du [mm] $108^2, 108^4, 108^8, 108^{16}, \ldots$ [/mm] jeweils natürlich mod 113.
Für [mm] $108^{13}$ [/mm] mußt du jetzt nur noch die Tabellenwerte [mm] $108^8 [/mm] * [mm] 108^4 [/mm] * 108$ multiplizieren und das ist leicht.
Gruß
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:50 Fr 18.01.2008 | | Autor: | Lee1601 |
also einfach 108 mit den 2er potenzen jeweils mod. 119 und dann die ergebnisse multiplizieren? und so kommt man auf 10? scheint mir etwas seltsam....kannst du mir das an dem beispiel mal zeigen? bei der zettelaufgabe haben wir noch viel größere zahlen
danke
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:14 Fr 18.01.2008 | | Autor: | koepper |
Hallo Lee,
vorrechnen darfst DU hier.
Ich sage dir dann ob es stimmt 
LG
Will
|
|
|
|
