Übung 9 Aufgabe G2 Fehler?

amy_starfish
Neuling
Neuling
Beiträge: 8
Registriert: 20. Feb 2006 13:08

Übung 9 Aufgabe G2 Fehler?

Beitrag von amy_starfish »

hallo, gitb's überhaupt nen Fehler bei der Musterlösung?

also bei G2(RSA und Chinesischer Restsatz)
.......
c hoch d = 5817*4500*9001+6998*[highlight=red]4500[/highlight]*8999 = ......


4500? ich denke hier sollte -4499 sein
da 8999*4500+9001*(-4499)=1

bubumiha
Windoof-User
Windoof-User
Beiträge: 31
Registriert: 21. Jan 2005 18:44
Wohnort: Frankfurt
Kontaktdaten:

Beitrag von bubumiha »

Es gilt eigentlich -4499 = 4500 mod 8999 .
Ich glaube, dass es egal ist, ob man -4499 oder 4500 nimmt, bin mir aber nicht 100% sicher.

Evgeni
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 1. Dez 2004 19:22

Beitrag von Evgeni »

bubumiha hat geschrieben:Es gilt eigentlich -4499 = 4500 mod 8999 .
Ich glaube, dass es egal ist, ob man -4499 oder 4500 nimmt, bin mir aber nicht 100% sicher.
du kannst alles nehmen was von der form 4500 + n\( \dot \mathbb{Z}
\)
ist

Pinky
Erstie
Erstie
Beiträge: 18
Registriert: 15. Dez 2005 01:37

Beitrag von Pinky »

du kannst alles nehmen was von der form 4500 + n \dot \mathbb{Z} ist
Nun ist n aber 8999*9001 und damit ist 4500 nicht kongruent -4499 mod n ...

Es kommt also auch was anderes raus, wenn man es mit -4499 rechnet ... wieso wird in der MuLö mit 4500 gerechnet? Der erweiterte Euklid meint jedenfalls wie der OP bereits sagte -4499 und da wir auch nicht groß modulo gerechnet ... kapier das irgendwie nicht und wäre für einen tip dankbar ...

bubumiha
Windoof-User
Windoof-User
Beiträge: 31
Registriert: 21. Jan 2005 18:44
Wohnort: Frankfurt
Kontaktdaten:

Beitrag von bubumiha »

Da wird CRT benutzt, d.h.
c^d == (5817*y1*9001 + 6998*y2*8999) mod 8999*9001
Dabei gilt:

y1*9001 == 1 mod 8999
und
y2*8999 == 1 mod 9001.

Es gilt dann weiter :
y1 == -4499 mod 8999 === 4500 mod 8999.

Also, man kann entweder -4499 oder 4500 benutzen, um c^d zu berechnen.

Pinky
Erstie
Erstie
Beiträge: 18
Registriert: 15. Dez 2005 01:37

Beitrag von Pinky »

bubumiha hat geschrieben: Also, man kann entweder -4499 oder 4500 benutzen, um c^d zu berechnen.
Dann bin ich entweder zu blöd zum rechnen (was nicht besonders abwegig ist), oder aber ich verstehe was nicht.

c^d = 5817*4500*9001+6998*4500*8999 = 3519107 mod n (wie in MuLö)
c^d = 5817*4500*9001-6998*4499*8999 = -858087 mod n = 80141912 mod n

wobei n = 8999*9001 = 80999999

Zwei verschiedene Ergebnisse für c^d macht doch auch keinen Sinn, oder?

bagotios
Mausschubser
Mausschubser
Beiträge: 72
Registriert: 1. Dez 2004 15:54

Beitrag von bagotios »

Muß man nicht immer den kleinsten nicht negativen Wert benutzen?

bubumiha
Windoof-User
Windoof-User
Beiträge: 31
Registriert: 21. Jan 2005 18:44
Wohnort: Frankfurt
Kontaktdaten:

Beitrag von bubumiha »

@pinky:
c^d = 5817*4500*9001-6998*4499*8999 = -858087 mod n = 80141912 mod n
Man muss "das andere 4500" ersetzen......also:
c^d = 5817*(-4499)*9001+6998*4500*8999 mod n = 35191907 mod 809999
Dann stimmt die Rechnung auch :)

@bagotios:
Wie jeff auch schon gesagt hat: Man kann jede Zahl nehmen, die in der Restklasse von -4499 liegt. Es ist aber natürlich am einfachsten, wenn man die kleinste Zahl nimmt :D

Pinky
Erstie
Erstie
Beiträge: 18
Registriert: 15. Dez 2005 01:37

Beitrag von Pinky »

ok ... das war jetzt unbefriedigend einfach :?

1000 dank! den verdrehten index hätte ich nie gefunden und mich vermutlich in der klausur noch gewundert ...

amy_starfish
Neuling
Neuling
Beiträge: 8
Registriert: 20. Feb 2006 13:08

Beitrag von amy_starfish »

jetzt ist es mir klar

die zwei 4500 haben unterschiedlichen Bedeutung!
wie zufällig!

danke euch alle!
Happy Valentine's Day! (eigentlich keine wegen der Klausur :( )

Antworten

Zurück zu „Archiv“