Übung 3.1 b)

Elementer
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 14. Mär 2009 14:56

Übung 3.1 b)

Beitrag 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

Parasiris
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 1. Okt 2007 16:04

Re: Übung 3.1 b)

Beitrag von Parasiris »

für x kommt -17 raus

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

Gruß

Elementer
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 14. Mär 2009 14:56

Re: Übung 3.1 b)

Beitrag 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

Remake
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 15. Dez 2007 10:40

Re: Übung 3.1 b)

Beitrag 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.

Elementer
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 14. Mär 2009 14:56

Re: Übung 3.1 b)

Beitrag von Elementer »

Hm ok,

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

Gruß
Steffen

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Übung 3.1 b)

Beitrag 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.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

Antworten

Zurück zu „Archiv“