Hausübung 6 (HNF)

Moderator: Post Quantum Cryptography

Richie
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 25. Okt 2005 13:03
Wohnort: Darmstadt
Kontaktdaten:

Hausübung 6 (HNF)

Beitrag von Richie » 21. Feb 2010 13:03

Hi,

könnte jemand von euch kurz skizzieren, wie man auf die HNF kommt? Ich bin schon damals nicht drauf gekommen und auch jetzt rate ich nur mit unimodularen Transformationen rum und komme auf nix gescheites. Hat irgendjemand Tipps?

Danke!
There are only 10 types of people in the world:
Those who understand binary and those who don't

Benutzeravatar
\Hannes
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 18. Nov 2005 17:24

Re: Hausübung 6 (HNF)

Beitrag von \Hannes » 21. Feb 2010 20:38

Es gibt da im Netz so diverse relativ (post-quantum-, hahaha) kryptische Anleitungen. Ich bin eigentlich gut damit gefahren, die Matrix auf obere Dreiecksgestalt zu bringen und dabei panisch aufzupassen, dass die Diagonalelemente schön groß sind. Dann auf den Teil oberhalb der Diagonalen konzentrieren und den Rest wegaddiern.
Schwabbeldiwapp hier kommt die Grütze.

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Re: Hausübung 6 (HNF)

Beitrag von marlic » 22. Feb 2010 10:20

Ich fands für den Beweis der eindeutigkeit auch ziemlich hilfreich, sich die allgemeine Methode, auf die HNF zu kommen, anzuschauen.
"Copy & Passed"

Wahlspruch der Plagiatoren

Richie
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 25. Okt 2005 13:03
Wohnort: Darmstadt
Kontaktdaten:

Re: Hausübung 6 (HNF)

Beitrag von Richie » 22. Feb 2010 13:30

Danke auf jeden Fall schonmal.
Ich habe ja auch gesucht, aber ich habe da keinen Algorithmus zu gefunden (außer: "mach Gauß mit unimodularen Transformationen").
Hat da jemand evtl. einen Link?
There are only 10 types of people in the world:
Those who understand binary and those who don't

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Re: Hausübung 6 (HNF)

Beitrag von marlic » 23. Feb 2010 17:54

Also ich habs heute nochmal probiert und bin auf folgenden Algorithmus gekommen:

Teil 1. Auf obere Dreiecksgestalt bringen:
Dazu jeweils - wie im euklidischen Algorithmus - das kleinste Element der Zeile von den anderen abziehen, sodass sie gerade noch positiv bleiben. Dass eben so lange machen, bis nur noch ein Eintrag in der Zeile >0 ist, den dann ganz nach rechts tauschen. Sollte einer der Einträge mal < 0 sein, einfach die Spalte mal -1 nehmen. Generell sind die hier genannten Operationen Spaltenoperationen.

Teil 2. HNF sicherstellen:
Wieder von unten nach oben vorgehen, alle Einträge rechts der Diagonalen modulo der Diagonale reduzieren, also sooft die Spalte mit der diagonalen abziehen / addieren, dass der jeweilige Eintrag kleiner dem Diagonaleintrag und nichtnegativ ist. Auch hier sind die Operationen als Spaltenoperationen zu verstehen.

Ich hoffe es hilft euch noch ;)

Michi
"Copy & Passed"

Wahlspruch der Plagiatoren

Benutzeravatar
C0RNi666
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 114
Registriert: 8. Jan 2008 12:51

Re: Hausübung 6 (HNF)

Beitrag von C0RNi666 » 23. Feb 2010 18:36

Find ich gut, dass du deine Idee gepostet hast ;)
Win32: Reboot!
Unix: Be root!

Richie
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 25. Okt 2005 13:03
Wohnort: Darmstadt
Kontaktdaten:

Re: Hausübung 6 (HNF)

Beitrag von Richie » 23. Feb 2010 19:03

Schonmal super vielen Dank auch dafür, bin aber noch etwas verwirrt :)
marlic hat geschrieben:Also ich habs heute nochmal probiert und bin auf folgenden Algorithmus gekommen:
Teil 1. Auf obere Dreiecksgestalt bringen:
Dazu jeweils - wie im euklidischen Algorithmus - das kleinste Element der Zeile von den anderen abziehen, sodass sie gerade noch positiv bleiben. Dass eben so lange machen, bis nur noch ein Eintrag in der Zeile >0 ist, den dann ganz nach rechts tauschen. Sollte einer der Einträge mal < 0 sein, einfach die Spalte mal -1 nehmen. Generell sind die hier genannten Operationen Spaltenoperationen.
Was genau meinst du mit "kleinstes Element"? Also wahrscheinlich 'ne Zahl, aber ich kann ja nur Zeilen von Zeilen oder Spalten von Spalten abziehen, oder? Also kann ich mir doch mit einer Zeile 'ne andere kaputt machen?
Meinst du den Gauß statt den euklidischen Algorithmus? Wenn nicht, weiß ich nicht, welchen Algorithmus du meinst :)
Teil 2. HNF sicherstellen:
Wieder von unten nach oben vorgehen, alle Einträge rechts der Diagonalen modulo der Diagonale reduzieren, also sooft die Spalte mit der diagonalen abziehen / addieren, dass der jeweilige Eintrag kleiner dem Diagonaleintrag und nichtnegativ ist. Auch hier sind die Operationen als Spaltenoperationen zu verstehen.
There are only 10 types of people in the world:
Those who understand binary and those who don't

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Re: Hausübung 6 (HNF)

Beitrag von marlic » 24. Feb 2010 07:18

"Generell sind die hier genannten Operationen Spaltenoperationen." Damit meine ich, dass man jedes "<Prädikat> Element in der aktuellen Zeile" im Text durch "Spalte, die das <Prädikat> Element in der aktuellen Zeile enthält" ersetzen muss.
"Copy & Passed"

Wahlspruch der Plagiatoren

Antworten

Zurück zu „Post-Quantum Cryptography“