RSA verschlüsselung < Moduln/Vektorraum < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
hallo,
kann mir einer helfen das auszurechnen, ich bekomme eine komische Zahl raus...
danke euch schon mal
|
|
| |
|
> 77d mod 120=1
> hallo,
> kann mir einer helfen das auszurechnen, ich bekomme eine
> komische Zahl raus...
Dann zeig' doch zuerst mal, wie du vorgegangen bist
und weshalb dir dein Ergebnis "komisch" erscheint !
LG
|
|
|
| |
|
ich dachte ich löse das so:
77d mod 120=1
77d=1 mod 120
d= (1 mod 120)/77
d= 1/77
ich bin mir eigentlich ziemlich sicher dass das nicht richtig ist...:o(
> > 77d mod 120=1
>
> > hallo,
> > kann mir einer helfen das auszurechnen, ich bekomme
> eine
> > komische Zahl raus...
>
>
> Dann zeig' doch zuerst mal, wie du vorgegangen bist
> und weshalb dir dein Ergebnis "komisch" erscheint !
>
> LG
>
|
|
|
| |
|
hat vlt jmd eine Idee wie man das lösen kann,
danke schön
|
|
|
| |
|
> 77d mod 120=1
> hat vlt jmd eine Idee wie man das lösen kann,
> danke schön
Hallo,
was du brauchst, ist eine Methode für die modulare
Division, zum Beispiel den erweiterten Euklidischen
Algorithmus.
Darüber kannst du dich beispielsweise![[]](/images/popup.gif) da schlau
machen. Es werden dort auch Beispiele durchge-
rechnet.
Gruß Al-Chw.
|
|
|
| |
|
Hallo!
Du musst eine *natürliche* Zahl d finden, sodass 77d bei Division durch 120 den Rest 1 lässt.
1/77 ist selbstverständlich keine natürliche Zahl.
Gruß
TW
|
|
|
| |
|
das weiß ich ,aber ich weiß nicht wie ich das rechnen muss..
|
|
|
| |
|
du musst das ganze in eine gleichung der form
d=15+142n bringen, wobei n eine natürliche Zahl ist.
kennst du die diophantische Gleichung ?
|
|
|
| |
|
ja das wäre dann ja:
77d+120x=1
ich komme da auf kein ergebnis:O(
|
|
|
| |
|
die gleichung selbst stimmt, nur musst du sie noch lösen indem du zuerst den ggt bestimmst, und danach rekursiv die partikulärlösungen, in deinem fall würde das so aussehen(wenn du vorher den ggt durch euklid ausgerechnet und aufgeschrieben hast wirst du sehen wie ich darauf komme!):
1 = 1*7 + (-3*2)
= -3*9 + (4*7)
= 4*34 + (-15*9)
das machst du jetzt so lange
bis du dahin kommst, wo je 77 und 120 "beteiligt" sind:
(in deinem fall:
1=(-34*120) + (53*77)
damit hast du jetzt die partikulären lösungen [mm] (x_{0}=-34 [/mm] und [mm] d_{0}=53), [/mm]
dadurch auch die endlösung:
d= 53+120n
|
|
|
| |
|
ohh danke schön,
darf ich fragen wie schnell du dadrauf gekommen bist?
ich rechne die schon voll laNGE AUS UND ES NIMMT kein Ende
ich habe das immer so gemacht:
1)ggT(77,120) ausgerechnet
2) rückwärts Rechnung d.h.
1=(3-2)=(5-2)-(9-7).....=((((25-9)-(43-34))-(43-34)-(16-9))))......und so weiter es nimmt kein Ende, kann man das irgendwie schneller machen?
Vielen Dank
|
|
|
| |
|
Hallo katinkas-dream,
> ohh danke schön,
> darf ich fragen wie schnell du dadrauf gekommen bist?
> ich rechne die schon voll laNGE AUS UND ES NIMMT kein
> Ende
> ich habe das immer so gemacht:
> 1)ggT(77,120) ausgerechnet
> 2) rückwärts Rechnung d.h.
>
> 1=(3-2)=(5-2)-(9-7).....=((((25-9)-(43-34))-(43-34)-(16-9)))) ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]") ......und
> so weiter es nimmt kein Ende, kann man das irgendwie
> schneller machen?
Ich verstehe die Zeile darüber nicht ganz, aber für das Rückwärtseinsetzen gibt's keine Abkürzung (zumindest kenne ich keine)
Es ist doch (Euklid. Algo):
[mm] $120=1\cdot{}77+43$
[/mm]
[mm] $77=1\cdot{}43+34$
[/mm]
[mm] $43=1\cdot{}34+9$
[/mm]
[mm] $34=3\cdot{}9+7$
[/mm]
[mm] $9=1\cdot{}7+2$
[/mm]
[mm] $7=3\cdot{}2+\red{1}$
[/mm]
[mm] $2=2\cdot{}1+0$
[/mm]
Damit [mm] $\ggT(120,77)=\red{1}$
[/mm]
Nun rückwärts (beginnend mit der vorletzten Zeile und dann zeilenweise aufwärts):
[mm] $1=7-3\cdot{}\blue{2}=7-3\cdot{}\blue{(9-1\cdot{}7)}=4\cdot{}\green{7}-3\cdot{}9$
[/mm]
[mm] $=4\cdot{}\green{(34-3\cdot{}9)}-3\cdot{}9=4\cdot{}34-15\cdot{}\blue{9}$
[/mm]
[mm] $=4\cdot{}34-15\cdot{}\blue{(43-1\cdot{}34)}=19\cdot{}\green{34}-15\cdot{}43$
[/mm]
[mm] $=19\cdot{}\green{(77-1\cdot{}43)}-15\cdot{}43=19\cdot{}77-34\cdot{}\blue{43}$
[/mm]
[mm] $=19\cdot{}77-34\cdot{}\blue{(120-1\cdot{}77)}$
[/mm]
[mm] $=\red{-34\cdot{}120+53\cdot{}77}$
[/mm]
>
> Vielen Dank
LG
schachuzipus
|
|
|
| |
|
warum ist d= 53+120n und nicht gleich 53, weil 53 ist ja auch eine ganze zahl und 77*53 mod 120= 1 stimt auch warum dann noch +120n dazu?
|
|
|
| |
|
> warum ist d= 53+120n und nicht gleich 53, weil 53 ist ja
> auch eine ganze zahl und 77*53 mod 120= 1 stimt auch warum
> dann noch +120n dazu?
Hallo,
in der Tat ist d=53 eine Lösung Deiner Gleichung 77d=1 mod 120.
Deine Aufgabe ist nun etwas spärlich gestellt, Du verrätst nämlich gar nicht genau, was Du tun sollst. Sollst Du eine Lösung finden?
Alle ganzen Zahlen finden, die die Gleichung lösen? Alle Lösungen zwischen 0 und 119 finden?
Es sind nunmal alle Zahlen der Machart [mm] d_n=53+120n (n\in \IZ) [/mm] Lösungen Deiner Gleichung,
also z.B.
[mm] d_{-123}=53+120*(-123)
[/mm]
[mm] d_{-3}=53+120*(-3)
[/mm]
[mm] d_0=53+120*0
[/mm]
[mm] d_{1}=53+120*1
[/mm]
[mm] d_{17}=53+120*17.
[/mm]
Prüfe das nach.
Allgemein
[mm] 77*d_n=77*(53+120_n)=77*53 [/mm] + [mm] 77*120n\equiv77*53\equiv [/mm] 1 (mod 120).
Gruß v. Angela
|
|
|
| |
|
> > warum ist d= 53+120n und nicht gleich 53, weil 53 ist ja
> > auch eine ganze zahl und 77*53 mod 120= 1 stimt auch warum
> > dann noch +120n dazu?
> Deine Aufgabe ist nun etwas spärlich gestellt, Du verrätst
> nämlich gar nicht genau, was Du tun sollst. Sollst Du eine
> Lösung finden?
> Alle ganzen Zahlen finden, die die Gleichung lösen? Alle
> Lösungen zwischen 0 und 119 finden?
Hallo Angela und katinkas-dream,
im Rahmen der RSA-Verschlüsselung ist natürlich nur
die Lösung modulo 120 von Interesse. Man kann also
auf das " [mm] +120\,n [/mm] " verzichten.
Gruß Al-Chwarizmi
|
|
|
| |
|
kennst du den euklidischen Algorithmus?
|
|
|
|
