Sonderfall in RSA: m=p < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich beschäftige mich zur Zeit mit RSA. Und ich frage mich, wie man beweisen kann, dass die Formeln auch für den Sonderfall m=p (bzw. m=q) gültig sind. Hier ist der Satz von Euler ja nicht direkt anwendbar, da m und n (bzw. in der Euler-Formel a und n) nicht teilerfremd sind. Falls jemand einen Beweis parat hat oder mir einen Link geben kann, dann wäre ich ihm sehr verbunden.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
LG Felix
|
|
| |
|
Habe nach weiterer Recherche bei Wikipedia einen Link zum ![[]](/images/popup.gif) Beweis gefunden. Dort wird mit dem Chinesischen Restsatz argumentiert, den ich noch nicht kenne, aber den in mein Referat einzubauen wäre zu aufwendig, deshalb werde ich auf ihn verweisen aber den Beweis nicht erläutern.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:45 Di 14.10.2014 | | Autor: | Marcel |
Hallo,
> Hallo,
>
> ich beschäftige mich zur Zeit mit RSA. Und ich frage mich,
> wie man beweisen kann, dass die Formeln auch für den
> Sonderfall m=p (bzw. m=q) gültig sind. Hier ist der Satz
> von Euler ja nicht direkt anwendbar, da m und n (bzw. in
> der Euler-Formel a und n) nicht teilerfremd sind. Falls
> jemand einen Beweis parat hat oder mir einen Link geben
> kann, dann wäre ich ihm sehr verbunden.
schreib' mal bitte, welche Formeln genau Du meinst und was die
Variablen bedeuten.
Informationen zu dem Verfahren findest Du eigentlich schnell: Ich habe
es etwa in "Elementare und algebraische Zahlentheorie" von Müller-Stach,
Piontkowski, gesehen, auch in "Einführung in die Kryptographie" von
Johannes Buchmann.
Aber man findet es auch im Netz erklärt, bspw.:
http://math-www.upb.de/~acrowley/Tutorien/img/elemZahlentheorie.pdf
http://www.math.uni-trier.de/~mueller/EZA2011_include.pdf -> Seite 35 ff.
[mm] $\varphi$ [/mm] ist dabei die Eulersche Phi-Funktion, [mm] $\varphi(n)$ [/mm] *zählt*
die Anzahl der Einheiten in [mm] $\IZ/(n\IZ)$, [/mm] also [mm] |(\IZ/(n \IZ))^\times|!
[/mm]
Gruß,
Marcel
|
|
|
| |
|
Vielen Dank für die Zeit, die du dir genommen hast. Siehe jedoch die Mitteilung, die ich gemacht habe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:10 Mi 15.10.2014 | | Autor: | Marcel |
Hallo,
> Vielen Dank für die Zeit, die du dir genommen hast. Siehe
> jedoch die Mitteilung, die ich gemacht habe.
kein Thema.
Nebenbei: Schon in dem ersten Link von mir sehe ich aber nicht, wo man
da der Chinesische Restsatz gebraucht werden würde. Ich sehe nur den
kleinen Fermat. (Kann aber sein, dass ich da etwas überlese - er geht
nämlich an anderer Stelle durchaus ein bzw. wird erwähnt!)
Gruß,
Marcel
|
|
|
|
