Erweiterter Euklidscher Algorithmus |
15.01.2009, 18:09 | caringandkilling | Auf diesen Beitrag antworten » | ||
Erweiterter Euklidscher Algorithmus ich habe ein gewaltiges Problem mit dem EEA, und zwar gelingt es mir nicht ihn korrekt anzuwenden. Die Aufgabe lautet wie folgt: Bestimme das modulare Inverse zu 73 in in Z(800), also den Faktor x * 73 modulo 800 = 1. Zunächst vergewissere ich mich dass ein Inverses existiert, dazu verwende ich den EA zur Bestimmung des ggT(73,800): 800=10*73+70 73=1*70+3 70=23*3+1 3=3*1+0 Also ist der ggT(73,800)=1 Folglich gibt es ein modulares Inverses zu 73 in Z(800). Nun möchte ich das Ganze von Hinten wieder aufrollen um das Inverse zu bestimmen: 1=1*70-23*3................................//vorletzte Gleichung nach 1 umgestellt 1=1*70-23*(73-1*70)....................//die 3 durch die zweite Gleichung substituiert 1=2*70-23*73..............................//nach Resten geordnet 1=2*(800-10*73)-23*73................//die 70 durch die erste Gleichung substituiert 1=2*800-33*73............................//nach Resten geordnet Soweit so gut, eigentlich sollte der Faktor vor der 73 nun dem gesuchten Inversen entsprechen. Tut er aber nicht!!!! Ich bin jetzt seit mehreren Stunden dabei zu versuchen dieses Schema zu durchblicken, komme aber nicht auf den grünen Ast. HILFE!!!! |
||||
15.01.2009, 19:28 | AD | Auf diesen Beitrag antworten » | ||
Ohne Worte...
1=24*70-23*73 |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|