Erweiterter Euklid

Gerrit
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 13. Okt 2010 20:29

Erweiterter Euklid

Beitrag von Gerrit »

Muss ich in der Klausur eigentlich das Verfahren aus der Vorlesung benutzen oder kann ich das (weitaus einfachere) Verfahren aus der Krypto-Vorlesung verwenden, in dem ich die Minuswelle erst am Ende einrechne? Ich verhaue mich bei dem Verfahren hier aus der Vorlesung imme rirgendwo..

Benutzeravatar
hymGo
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 209
Registriert: 4. Okt 2009 23:17

Re: Erweiterter Euklid

Beitrag von hymGo »

Das Verfahren auf den Vorlesungsfolien hat meines Wissens irgendwo einen Fehler.
Soweit ich weiß darf man das Verfahren seiner Wahl verwenden.

FidorDewski
Erstie
Erstie
Beiträge: 13
Registriert: 8. Mär 2011 18:29

Re: Erweiterter Euklid

Beitrag von FidorDewski »

Das wäre mal interessant zu wissen, bevor ich mir das jetzt aneigne und es falsch ist. In der Übung hat es eigentlich geklappt, wenn ich das richtig sehe, müsste ich aber nochmal durchrechnen. Hast du eine zuverlässige Info, ob es tatsächlich falsch ist und wo der Fehler steckt?

Benutzeravatar
hymGo
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 209
Registriert: 4. Okt 2009 23:17

Re: Erweiterter Euklid

Beitrag von hymGo »

Also für die Hausübung hab ich ihn direkt so implementiert(kopiert) wie es auf der Folie steht und er hat nicht die richtigen Ergebnisse geliefert. Anscheinend ist irgendwas von den "Bennungen" vertauscht oder so. Also mir wars dann auch zu blöd den Fehler(falls es wirklich einer ist und ich nicht zu blöd fürs kopieren war) zu suchen und ich hab ne andere Version verwendet.
Also ich persönlich finde die Euklid Version aus der folgenden Zusammenfassung ziemlich gut. Da muss man sich einfach viel weniger merken als bei der Skript Variante.
http://www.d120.de/forum/viewtopic.php?f=199&t=21611

Benutzeravatar
AlexPi11
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 18. Apr 2009 15:32

Re: Erweiterter Euklid

Beitrag von AlexPi11 »

Also ich benutze den Algo. aus den Folien und das ging eigentlich ganz gut; kann aber sein, dass ich den Fehler überlesen hab' . :D
Per Hand kann man den aber gut abändern, indem man statt 4 Extra-Spalten für die alten x- und y-Werte, einfach zwei zusätzliche Zeilen am Anfang benutzt. Aber das in der Zusammenfassung ist auch nicht schlecht. Ist das der Alog. aus der Krypto-Vorlesung oder ist das nochmal eine andere Variante?

Benutzeravatar
hymGo
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 209
Registriert: 4. Okt 2009 23:17

Re: Erweiterter Euklid

Beitrag von hymGo »

Soweit ich weiß ist das der Algorithmus aus der Mathe 1 Vorlesung.

Gerrit
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 13. Okt 2010 20:29

Re: Erweiterter Euklid

Beitrag von Gerrit »

Der aus der Krypto-Vorlesung kommt mit vier Zeilen (oder bei 90°-Drehung mit vier Spalten) aus: Rest, Divisor, X, Y

findest du auf Seite 4 der folgenden Zusammenfassung: http://www.d120.de/forum/viewtopic.php?f=409&t=20957
Zu ebachten ist hier, dass die Minuswelle am Ende eingerechnet werden muss - bei x jedes zweite beginnend bei dem zweiten und bei y jedes zweite beginnend bei dem ersten (deshalb auch welle, weil x und y abwechselns - sind....)

Auf der selben Seite ist auch ein Verfahren zur schnellen Exponentation, was ebenfalls recht kompakt ist und schnell geht!

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Erweiterter Euklid

Beitrag von dschneid »

hymGo hat geschrieben:Also für die Hausübung hab ich ihn direkt so implementiert(kopiert) wie es auf der Folie steht und er hat nicht die richtigen Ergebnisse geliefert. [...]
Ich hatte damit auch Probleme, das lag aber daran, dass der Algorithmus auch negative Zahlen zurückgibt, und bei der Verwendung zum Invertieren hat das dann später Probleme verursacht. Als ich das Resultat dann gegebenenfalls noch in ein äquivalentes positives umgewandelt habe, lief alles. Deine Probleme müssen also nicht unbedingt vom Algorithmus selbst herrühren. Beim Rechnen von Aufgaben von Hand hat er mit bis jetzt auch immer richtige Ergebnisse geliefert.

Benutzeravatar
truongln88
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 31. Jan 2010 19:17
Kontaktdaten:

Re: Erweiterter Euklid

Beitrag von truongln88 »

hymGo hat geschrieben:Das Verfahren auf den Vorlesungsfolien hat meines Wissens irgendwo einen Fehler.
Soweit ich weiß darf man das Verfahren seiner Wahl verwenden.
Der Fehler auf den Folien liegt daran, dass \(y = y_{k}y_{k-1}\dots y_1\) statts \(y = y_1y_2\dots y_{k}\) im Algorithmusbeschreibung.

Antworten

Zurück zu „Archiv“