Erklärung der Gleichung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:28 Do 17.04.2008 | | Autor: | DAB268 |
| Aufgabe | | [mm] 27^{-1}=3 \mod [/mm] 40 |
Hallo.
Kann mir einer erklären, wie ich auf die 3 komme?
MfG
DAB268
|
|
| |
|
> [mm]27^{-1}=3 \mod 40[/mm]
> Hallo.
>
> Kann mir einer erklären, wie ich auf die 3 komme?
Die Aufgabe scheint mir ein bisschen sonderbar, da im Ring der ganzen Zahlen modulo 40 die Division eigentlich nicht generell eindeutig definiert ist.
Sucht man eine Zahl [mm] n (n \in \IN) [/mm] so, dass [mm] n * 27 = 1 \ (mod \ 40)[/mm] , dann ist natürlich [mm] n=3[/mm] eine Lösung, weil [mm]3*27 = 81 = 2*40 + 1[/mm], also [mm](3*27)\ mod \ 40 =1[/mm] .
Um besser helfen zu können, müsste man wissen in welchem Zusammenhang und auf welchen Vorkenntnissen aufbauend die Frage gestellt wurde.
Die Frage nach [mm] 10^{-1} [/mm] mod 40 wäre aber zum Beispiel sinnlos, da es dann keine Lösung gibt.
Gruss al-Ch.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:27 Do 17.04.2008 | | Autor: | DAB268 |
Hallo.
Danke für die Antwort!
Hier mal der Zusammenhang:
Alice und Bob wollen über RSA-Verschlüsselung kommunizieren.
Alice wählt [mm] p=5,q=11\Rightarrow n=p\cdotq=55
[/mm]
[mm] \phi(n)=4\cdot10=40
[/mm]
Alice wählt [mm] e=27(\ggT(27,40)=1)
[/mm]
Nun muss Alice d berechnen: [mm] d=e^{-1}=27^{-1}=3 \mod40
[/mm]
Hoffe das hilft weiter.
MfG
DAB268
|
|
|
| |
|
> Hallo.
>
> Danke für die Antwort!
>
> Hier mal der Zusammenhang:
>
> Alice und Bob wollen über RSA-Verschlüsselung
> kommunizieren.
>
> Alice wählt [mm]p=5,q=11\Rightarrow n=p\cdotq=55[/mm] <--------??? 5 = 55 ?
>
> [mm]\phi(n)=4\cdot10=40[/mm]
> Alice wählt [mm]e=27(\ggT(27,40)=1)[/mm]
> Nun muss Alice d berechnen: [mm]d=e^{-1}=27^{-1}=3 \mod40[/mm]
>
> Hoffe das hilft weiter.
>
O.K., wenn klar ist, dass [mm] ggT(e,\phi(n)) [/mm] = 1 ist, dann ist es eindeutig. Trotzdem finde ich es nicht sehr schön, hier die Bezeichnung [mm] e^{-1} [/mm] zu verwenden. wenn die Modulbasis keine Primzahl ist...
Aber es ist möglich, dass meine Ansicht da ein bisschen konservativ ist.
Sonst alles klar?
Gruss al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:35 Sa 19.04.2008 | | Autor: | felixf |
Hallo
> > Alice wählt [mm]p=5,q=11\Rightarrow n=p\cdotq=55[/mm]
> <--------??? 5 = 55 ?
Da war ein Tippfehler, er hat \cdotq geschrieben anstelle \cdot q.
> O.K., wenn klar ist, dass [mm]ggT(e,\phi(n))[/mm] = 1 ist, dann
> ist es eindeutig.
Dein Sprachgebrauch von `eindeutig' ist hier etwas ungewoehnlich: ich wuerde hier eher von Existenz sprechen! Das multiplikativ Inverse ist, soweit es denn existiert, eindeutig. Nur die Existenz ist nicht umbedingt klar. (In diesem Fall jedoch schon, wegen der Teilerfremdheit.)
> Trotzdem finde ich es nicht sehr schön,
> hier die Bezeichnung [mm]e^{-1}[/mm] zu verwenden. wenn die
> Modulbasis keine Primzahl ist...
Die Bezeichnung [mm] $e^{-1}$ [/mm] ist hier allerdings sehr gebraeuchlich, ich wuerde fast sagen Standard.
LG Felix
|
|
|
| |
|
Felix, du hast natürlich recht. Es geht um die Existenz: To be, or not to be ...
LG al-Chwarizmi
|
|
|
|
