Seite 1 von 1

Übung 3.1 b)

Verfasst: 14. Mär 2009 14:59
von Elementer
Servus,

ich steh irgendwie aufm Schlauch. Aber wie kommt man bei der 3.1 b), also die RSA Aufgabe, wo man d bestimmen soll auf d=103. Ich dacht wenn man den erweiterten euklidischen algo angewendet hat is man fertig und das x wär das ergebnis.

gruß
Steffen

Re: Übung 3.1 b)

Verfasst: 14. Mär 2009 15:12
von Parasiris
für x kommt -17 raus

d ist dann x mod n also -17 + 120 = 103, wenn ichs richtig verstanden habe

Gruß

Re: Übung 3.1 b)

Verfasst: 14. Mär 2009 15:14
von Elementer
Hm aber ich dacht es handelt sich hier um ne ganz normale lineare Kongruenz und dass x=d gilt.

wo steht das d= x mod n ist?

gruß
Steffen

Re: Übung 3.1 b)

Verfasst: 14. Mär 2009 15:51
von Remake
Steht in den Folien wohl nicht, aber es gilt: 1 < d < phi(n)

Du hast ja 7*d = 1 (mod 120)
Das gilt sowohl für d = -17 und wegen der o.g. Modulo Äquivalenz auch für d = 103 -> zweiteres erfüllt aber erst die Bedingung da oben.

Re: Übung 3.1 b)

Verfasst: 14. Mär 2009 15:55
von Elementer
Hm ok,

also es gilt allgemein wenn x<1, dann mach ich x mod n und nehm des ergebnis dann?

Gruß
Steffen

Re: Übung 3.1 b)

Verfasst: 14. Mär 2009 17:58
von bruse
Der Gag ist doch gerade, dass modulo n beide Zahlen äquivalent sind. Es ist unter diesem Gesichtspunkt also wurscht, welche Zahl du nimmst. Es hat sich aber eingebürgert (warum, könnt ihr selbst überlegen), den kleinsten nichtnegativen Repräsentanten einer Äquivalenzklasse zu nehmen.