erw. euklid. Algorithmus?!?!?! < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallöchen :)
Ich habe ein kleines Problem mit dem eEA. Stehe grade irgendwie auf der Leitung...
Also, wenn ich diese berühmten s und t ausrechnen will, so dass
ggT(a,b) = s*a + t*b
ist und das Ganze am Bsp. a=40 und b=13 durchspiele, dann komme ich auf die Lsg. s=1 und t= -3;
eine weitere Lsg. wäre aber s = -2 und t=27;
Wie kommt man auf die 2. Lösung, was sind die wesentlichen Unterschiede, welche ist die "richtige" Lösung, gibt es überhaupt eine richtige Lsg??
Da ich das ganze brauche zur Berechnung des geheimen Schlüssels beim RSA-Verfahren, wäre es gut, wenn ich bestimmen könnte, ob s oder t positiv sein soll!! Wie geht das??
Wäre sehr, sehr dankbar für eine Antwort!!
Gruß, Garfield
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:33 Mi 26.07.2006 | | Autor: | statler |
Guten Morgen Garfield!
> Ich habe ein kleines Problem mit dem eEA. Stehe grade
> irgendwie auf der Leitung...
>
> Also, wenn ich diese berühmten s und t ausrechnen will, so
> dass
>
> ggT(a,b) = s*a + t*b
>
> ist und das Ganze am Bsp. a=40 und b=13 durchspiele, dann
> komme ich auf die Lsg. s=1 und t= -3;
Das ist eben nicht die Lösung, sondern eine Lösung.
> eine weitere Lsg. wäre aber s = -2 und t=27;
Überhaupt nicht, rechne doch mal nach!
> Wie kommt man auf die 2. Lösung, was sind die wesentlichen
> Unterschiede, welche ist die "richtige" Lösung, gibt es
> überhaupt eine richtige Lsg??
Es ist doch
1 = 1*40 + (-3)*13
und außerdem
0 = (-13n)*40 + (40n)*13 für alle n [mm] \in \IZ
[/mm]
Wenn du diese beiden Gleichungen addierst, erhältst du ganz viele weitere Lösungen. Sogar alle.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
ok, alles klar! Danke für die Hilfe! 
|
|
|
|
