Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:04 So 02.02.2014 | | Autor: | spejt |
| Aufgabe | | e*d [mm] \equiv [/mm] 1 [mm] mod\varphi(N) [/mm] |
In meiner GFS über Kryphtographie bin ich auf, in Aufgabe 1 gezeigte, Kongruenz gestoßen.
Nun habe ich mir Kongruenz angeschaut, und denke auch verstanden:
Wenn a und b zu mod c kongruent sind, ist der jeweilige Modulo der gleiche...
Aber was bedeutet nun diese Kongruenz aus Aufgabe 1?
Wäre cool wenn mir das jemand mit einfachen Worten erklären könnte :)
|
|
| |
|
Hey spejt,
[mm] $\varphi(N)$ [/mm] ist eine natürliche Zahl, $e,d$ sind ebenfalls natürliche Zahlen. Nun kannst du $e*d$ mit Rest durch [mm] $\varphi(N)$ [/mm] teilen. Hierbei erhältst du einen eindeutigen Rest zwischen 0 und [mm] $\varphi(N)$. [/mm] Ist nun $e*d [mm] \equiv [/mm] 1 [mm] mod\varphi(N) [/mm] $, so heißt das, dass der Rest bei Division von $e*d$ durch [mm] $\phi(N)$ [/mm] genau $1$ ergibt.
Allgemeiner nochmal:
Seien $a,b,m [mm] \in \IN$ [/mm] natürliche Zahlen. Dann bedeutet
$a [mm] \equiv [/mm] b mod(n)$, dass $a$ und $b$ den gleichen Rest bei Division durch $n$ haben.
Dies ist äquivalent dazu, dass $a-b$ durch $n$ teilbar ist, wie du gern mal versuchen darfst zu beweisen. :)
lg
Schadow
PS: Für die Anwendung beim RSA Verfahren (ich nehm mal an darum geht es?) braucht man noch eine ganze Menge mehr Theorie und Wissen als nur die Frage, was eine Kongruenz ist. Sollten dabei also noch Fragen auftauchen dann immer gern her damit. ;)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:18 So 02.02.2014 | | Autor: | spejt |
| Aufgabe | | [mm] e*d\equiv1 mod(\phi(N)) [/mm] umformen in [mm] e*d+q*\phi(N)=1=ggT(e,\phi(N)) [/mm] |
Hey SchadowMaster,
erstmal vielen Dank für deine schnelle und freundliche Antwort! :)
Ah, du meinst weil 1mod(einer Zahl >1) immer 1 ergibt, muss durch die Kongruenz e*d [mm] mod(\phi(n)) [/mm] ja auch 1 sein...
:D Stimmt es geht um RSA und ich würde gleich von deinem Angebot gebrauch machen und die nächste Frage stellen: (Aufgabe1)
Also ich weiß das man diese Form braucht um mit dem erweiterten euklidischen Algorithmus dann das d auszurechnen, aber wie kommt man auf diese Umformung?
Also das der [mm] ggT(e,\phi(N)=1 [/mm] ist, ist logisch, da e ja teilerfremd zu [mm] \phi(N) [/mm] gewählt wurde aber ansonsten, komm ich da net ganz mit...
Grüße.
P.S. Puh beweißen... - vielleicht so? :)
[mm] a\equiv [/mm] b mod(n) -> a mod(n)=b mod(n) |-b mod(n), da die modulo-operation ja 0 ergeben muss wenn a-b durch n teilbar sein soll
-> a-b mod(n)=0
|
|
|
| |
|
Hallo spejt,
sorry, da ist Deine Frage irgendwie durchgegangen, und offenbar nicht nur mir.
> [mm]e*d\equiv1 mod(\phi(N))[/mm] umformen in
> [mm]e*d+q*\phi(N)=1=ggT(e,\phi(N))[/mm]
> [...]
>
> Ah, du meinst weil 1mod(einer Zahl >1) immer 1 ergibt, muss
> durch die Kongruenz e*d [mm]mod(\phi(n))[/mm] ja auch 1 sein...
![[haee]](/images/smileys/haee.gif "[haee]")
> :D Stimmt es geht um RSA und ich würde gleich von deinem
> Angebot gebrauch machen und die nächste Frage stellen:
> (Aufgabe1)
> Also ich weiß das man diese Form braucht um mit dem
> erweiterten euklidischen Algorithmus dann das d
> auszurechnen, aber wie kommt man auf diese Umformung?
> Also das der [mm]ggT(e,\phi(N)=1[/mm] ist, ist logisch, da e ja
> teilerfremd zu [mm]\phi(N)[/mm] gewählt wurde aber ansonsten, komm
> ich da net ganz mit...
Also ist auch [mm] \ggT{(d,\varphi(N))}=1.
[/mm]
Ansonsten wird hier nur das ![[]](/images/popup.gif) Lemma von Bézout angewandt.
> P.S. Puh beweißen... - vielleicht so? :)
> [mm]a\equiv[/mm] b mod(n) -> a mod(n)=b mod(n) |-b mod(n), da die
> modulo-operation ja 0 ergeben muss wenn a-b durch n teilbar
> sein soll
> -> a-b mod(n)=0
Bis dahin gut. Jetzt musst Du nur noch anwenden, dass
[mm] a-b\equiv 0\bmod{n}\;\;\gdw\;\;a-b=k*n, k\in\IZ [/mm] ist.
Das ist einfach die Definition der Modulschreibweise, wo $k$ nicht interessiert, aber trotzdem existent ist.
Übrigens: es heißt beweisen.
Grüße
reverend
|
|
|
|
