Seite 1 von 3

Segment-LLL Verständnisfragen

Verfasst: 20. Mai 2008 16:05
von Cyrtox
So ganz klar ist mir das ganze ja immernoch nicht. Wir hatten beim letzten Treffen ja bereits eine kleine Diskussionsrunde. Aber machen wir das ganze einfach mal schriftlich weiter.

Also... wir wollen eine "primitive" Form des Segment-LLL implementieren.
- Wir bekommen eine Basis
- Diese Basis muss zunächst orthogonalisiert werden. Dazu ist eine QR-Zerlegung notwenig, korrekt? Habe im NTL-eigenen Code mal nachgesehen in Sachen LLL, habe dort aber keine Funktion gefunden, die eine QR-Zerlegung vornimmt? Zumindest nicht in 2 Matizzen. Nur eine zwei Funktionen, die die GS-Daten berechnen, allerdings sind diese schwer zu verstehen... sprich was da und vor allem wo rauskommt.
- Wie auch immer, die orthogonalisierte basis wird weitergegeben an den Loc-LLL. Hier wird die Submatrix (R^2kX2k) extrahiert und soll nun den normalen LLL durchlaufen und anschließend in die Matrix H (Z^2kX2k) gespeichert werden, richtig?
- Die zwei betrachteten Segmente sollen nun mit H multipliziert werden? (Welche Segmente... die in der Ursprungsbasis? Oder aus Q oder R?) Nehme an Ursprung bzw "bearbeiteter Ursprung" in den späteren Schritten. Schmließend soll das Segment (beide Segmente?) noch global reduziert werden... irgendwie?
- Dann noch die ominöse Abfrage und weiter gehts mit dem nächsten Segment, oder auch nicht, je nachdem.

Wie man sieht ist noch ziemlich viel etwas unklar. Vielleicht können hier ja einige weiterhelfen oder haben andere Fragen? Bringt mal etwas Leben ins Forum.

Re: Segment-LLL Verständnisfragen

Verfasst: 21. Mai 2008 20:32
von Cyrtox
Ok habe nun Stunden rumprobiert wie ich mit der NTL eine QR-Zerlegung machen kann... kein Erfolg. Die ComputeGS macht irgendetwas seltsames, egal wie ich die Ergebnisse dieser Funktion zusammensetze, sie ergeben nichts sinnvolles. Die IncrementalGS... ist unverständlich. Hat irgendjemand eine Idee wie ich an eine QR Zerlegung komme? Irgendwie muss ich ja an R kommen um Segment LLL zu implementieren. Und die Werte aus Q braucht man für den Check on man zum nächsten Segment übergeht oder nicht.

Re: Segment-LLL Verständnisfragen

Verfasst: 21. Mai 2008 22:13
von rlindner
Ich erinnere mich, dass das nicht ganz einfach war. Lest mal das Gitterskript von Schnorr (Seite 8 unten) da steht genau, was die Routine computeGS
http://www.shoup.net/ntl/doc/LLL.txt

Code: Alles auswählen

void ComputeGS(const mat_ZZ& B, mat_RR& mu, vec_RR& c);

// Computes Gramm-Schmidt data for B.  Assumes B is an m x n matrix of
// rank m.  Let if { B^*(i) } is the othogonal basis, then c(i) =
// |B^*(i)|^2, and B^*(i) = B(i) - \sum_{j=1}^{i-1} mu(i,j) B^*(j).
mit der QR-Zerlegung zu tun hat.

Re: Segment-LLL Verständnisfragen

Verfasst: 22. Mai 2008 04:27
von Cyrtox
Jo aus der txt werde ich leider nicht schlau. Durch die "Ersatzzeichen" ist es etwas schwer zu verstehen. Das mit dem Skript werde ich morgen nochmal versuchen...
Aber nochmal ganz wichtig... es ist definitiv so, dass man mit ComputeGS sowohl die Matrix Q als auch R berechnet bzw leicht errechnen kann? Weil die zurückgegebenen Daten irgendwie unverständlich sind. (mu = immer untere Dreiecksmatrix mit diagonale 0 und Zeilen/Spalten-Anzahl stimmt ebenfalls nicht mit Q oder R überein, c = vektor mit immer kleiner werdenden Werten) Naja wie gesagt morgen nochmal im Skript nachlesen, aber ob das bei der Funktion direkt hilft, mal sehen.

Re: Segment-LLL Verständnisfragen

Verfasst: 22. Mai 2008 16:42
von Cyrtox
Also aus den genannten Quellen werde ich nicht schlauer. computeGS liefert einen vektor und eine Matrix. im Vektor stehen schonmal nicht die ^b(i) werte, auch nicht die Länge dieser und auch nicht das quadrat... ka genau was uns c liefern soll. Und mu... da sollten doch die µ-Werte von GS drinstehen oder? Aber in dem Beispiel was ich benutze müssten diese glatt aufgehen, in mu stehen aber Kommazahlen. Zudem müsste das ganze in einer 3X3 Matrix stehen, da meine Basis 3 Spalten und 4 Zeilen hat. Aber computeGS liefert mir in mu eine 4x4 Matrix. Zudem ist die Diagonale und damit die eine Zeile und eine Spalte 0. Ich werde einfach nicht schlau draus... könnt ihr mir vielleicht sagen was computeGS liefert und WIE genau? Was steht in mu? Was steht in c? Und wie kann ich daraus R basteln? Ich brauche halt eigentlich die ||b(i)||'s und die µ's um ein R zu basteln...

Re: Segment-LLL Verständnisfragen

Verfasst: 26. Mai 2008 08:57
von rueckert
\(\mu\) is bereits die Gram-Matrix. Sie enthält Werte aus \(\mathbb{Q}\), die du mittels Skalierung ganzzahlig machen kannst. Der \(c\) Vektor hilft dir, wenn du die orthogonale Basis orthonormal machen willst.

Die Erklärung für die Dimensionsunterschiede hast du selbst gegeben. Da wurde ein Nullvektor ergänzt, um die Matrix quadratisch zu machen. Bitte schau die nochmal ein bisschen Literatur zu Gram-Schmidt und QR Zerlegung an. Es gibt dutzende Quellen hierzu.

Spätestens morgen nach der Präsentation sollte klar sein, wie es gemacht wird. Wenn ihr noch keine lauffähige Version habt, fehlt euch natürlich ein Zwischen-Feedback.

Re: Segment-LLL Verständnisfragen

Verfasst: 26. Mai 2008 13:36
von Cyrtox
Also ich teste ComputeGS halt mit einer Matrix deren QR zerlegung ich kenne. eine 3x4 matrix deren Q ebenfalls 3x4 ist und das R 3x3. Das Ergebnis von ComputeGS liefert aber eine 4x4 und selbst wenn ich den Nullvektor entferne und beliebig skaliere komme ich niemals auf das Q welches ich als Lösung kenne. Ok die müssen ja nicht gleich sein, aber wieso kommt bei ComputeGS bitte immer eine untere Dreiecksmatrix mit diagonale + Rest 0 raus? Das ergibt doch keinen Sinn. Habe rumgebastelt... die Ergebnismatrix verändert, transponiert, inveriert, in allen möglichen Variationen benutzt, aber ich komme auf kein sinnvolles Q bzw durch multiplikation kein R. Naja evtl weiss ja morgen jemand die Antwort... die Literatur bringt mich jedenfalls kein Stück weiter, wenn die Funktion etwas ganz anderes macht als in der Literatur steht, oder ich erkenne die offensichtliche Lösung nicht. Vielleicht ergibt sich morgen ja auch noch eine Lösung für die anderen zahlreichen Fragen zu SegmentLLL, die ich hier im Forum schonmal teilweise gestellt habe, schaun wir mal.

Re: Segment-LLL Verständnisfragen

Verfasst: 26. Mai 2008 14:56
von rueckert
Dass eine Dreiecksmatrix rauskommt ist nicht verwunderlich. Die Matrix wäre ansonsten symmetrisch und die Einsen auf der Diagonale wurden sicher aus Effizienzgründen weggelassen.

Re: Segment-LLL Verständnisfragen

Verfasst: 26. Mai 2008 17:07
von Cyrtox
Wie kann Q symmetrisch sein, wenn sie nXm mit n != m ist? Und einsen auf der Diagonalen muss sie auch nicht haben? Ach egal, schaun wir mal morgen wie das gemeint war.

Re: Segment-LLL Verständnisfragen

Verfasst: 26. Mai 2008 17:34
von rueckert
Gemeint war die Gram-Matrix, die im Prinzip normierte Skalarprodukte enthält.

Re: Segment-LLL Verständnisfragen

Verfasst: 2. Jun 2008 17:02
von Cyrtox
Ok kommen wir zu einigen neuen Fragen.

1. Beim letzten Treffen haben wir ja "festgestellt", dass sämtliche Matrizen quasi transponiert gespeiechert werden. Übrigens toll, dass die Ausgabefunktion über cout die Matrix trotzdem andersherum ausgibt und man sie sich dadurch immer transponiert vorstellen muss. Dadurch drehen sich auch SÄMTLICHE Operationen wie Matrixmultiplikationen um, oder? Sprich wenn ich beide Segmente * H rechnen muss, dann rechne ich im Code H * beide Segmente, wenn ich die Determinante ausrechne rechne ich Segment * Segment^T anstatt Segment^T * Segment usw. Ich hoffe das ist richtig, denn schon so richtet es ganz schön Verwirrung an!

2. Bei der Segment-LLL Abfrage ob ein Segment zurück oder eins weiter gesprungen werden soll braucht man die Determinanten beider Segmente. Ich habe bisher einfach ein einzelnes Segment extrahiert, es transponiert und dann B(l-1)^T * B(l-1) gerechnet, aus der resultierenden Matrix die Determinante und daraus die Wurzel. Das Ergebnis habe ich als Determinante des Segments l-1 genommen. Ist das so richtig? Ich habe noch eine andere Methode zur Berechnung der Determinante gesehen und zwar das aufmultiplizieren der Längenquadrate des Segments. Ka was nun richtig ist oder ob beides Richtig ist. Die Längenquadrate müsste man halt extra berechnen, was man ansonsten ja nicht machen muss.

3. Wieder bei der Abfrage aus 2., hier braucht man auch noch die Längenquadrate des ersten Vektors des Segments l-1 sowie des 2. Vektors aus dem selben Segment. Wie berechnet man diese? Muss man dazu die Längenquadrate aller Vektoren der Basis berechnen? Oder reicht es direkt im Segment l-1 zu beginnen? Ich nehme an, denn wir rechnen ja mit den beiden Segmenten bzw dem TEIL der R Matrix, der diese beiden Segmente betrifft und nicht mit der ganzen Basis. Es würden wohl andere Werte dabei herauskommen... denn rechnet man nur in l-1, dann wäre das erste Längenquadrat ja einfach das Skalarprodukt von bk(l-1) mit sich selbst!? Und das 2. wäre das Skalarprodukt von bk(l-1)+1 mit sich selbst und davon das erste Längenquadrat multipliziert mit irgendeinem µ^2, dieses µ entspricht hier dem Skalarprodukt aus bk(l-1) und bk(l-1)+1 korrekt!?

4. Für die Größenreduzierung brauchen wir wieder Die µs, diesmal aber von der gesamten Basis, da wir global vorgehen sollen!? Kann man die Werte irgendwie "einfach" updaten, denn sie stehen ja schon im Ergebnis der ComputeGS Funktion. Oder muss man sie jedes mal neu berechnen, wenn man zwei Segmente bearbeitet hat und diese zurück in die Basis B geschrieben hat? Laut dem Gitter.pdf Seite 35 ist die Längenreduktion in der For-Schleife berechenbar, die dort steht. Aber welche µs nimmt man? Die "aktualisierten" aus der darüberstehenden Berechnung? Oder werden die µ-Werte bereits durch den hinteren Teil der For-Schleife aktualisiert? Bzw. werden die Berechnung der µ-Werte im hinteren Teil der For-Schleife überhaupt in der µ-Matrix eingetragen oder braucht man die Veränderungen nur für die Längenreduzierung von B? Ok das klingt nun alles etwas verwirrend.

Es bestehen wie man sieht noch viele Stolpersteine. Es ist etwas schwer den eigenen Code zu testen, wenn der Fehler überall sein könnte. ;)

Re: Segment-LLL Verständnisfragen

Verfasst: 2. Jun 2008 17:32
von rueckert
1. Beim letzten Treffen haben wir ja "festgestellt", dass sämtliche Matrizen quasi transponiert gespeiechert werden. Übrigens toll, dass die Ausgabefunktion über cout die Matrix trotzdem andersherum ausgibt und man sie sich dadurch immer transponiert vorstellen muss. Dadurch drehen sich auch SÄMTLICHE Operationen wie Matrixmultiplikationen um, oder? Sprich wenn ich beide Segmente * H rechnen muss, dann rechne ich im Code H * beide Segmente, wenn ich die Determinante ausrechne rechne ich Segment * Segment^T anstatt Segment^T * Segment usw. Ich hoffe das ist richtig, denn schon so richtet es ganz schön Verwirrung an!
Die NTL speichert alle Matrizen in Zeilenschreibweise. Dementsprechend müssen auch alle Basiswechsel auf Zeilen ausgeführt werden.
2. Bei der Segment-LLL Abfrage ob ein Segment zurück oder eins weiter gesprungen werden soll braucht man die Determinanten beider Segmente. Ich habe bisher einfach ein einzelnes Segment extrahiert, es transponiert und dann B(l-1)^T * B(l-1) gerechnet, aus der resultierenden Matrix die Determinante und daraus die Wurzel. Das Ergebnis habe ich als Determinante des Segments l-1 genommen. Ist das so richtig? Ich habe noch eine andere Methode zur Berechnung der Determinante gesehen und zwar das aufmultiplizieren der Längenquadrate des Segments. Ka was nun richtig ist oder ob beides Richtig ist. Die Längenquadrate müsste man halt extra berechnen, was man ansonsten ja nicht machen muss.
Steht im Schnorr Skript. Die Determinante ist eindeutig und kann sicher auf verschiedene Weisen berechnet werden.
3. Wieder bei der Abfrage aus 2., hier braucht man auch noch die Längenquadrate des ersten Vektors des Segments l-1 sowie des 2. Vektors aus dem selben Segment. Wie berechnet man diese? Muss man dazu die Längenquadrate aller Vektoren der Basis berechnen? Oder reicht es direkt im Segment l-1 zu beginnen? Ich nehme an, denn wir rechnen ja mit den beiden Segmenten bzw dem TEIL der R Matrix, der diese beiden Segmente betrifft und nicht mit der ganzen Basis. Es würden wohl andere Werte dabei herauskommen... denn rechnet man nur in l-1, dann wäre das erste Längenquadrat ja einfach das Skalarprodukt von bk(l-1) mit sich selbst!? Und das 2. wäre das Skalarprodukt von bk(l-1)+1 mit sich selbst und davon das erste Längenquadrat multipliziert mit irgendeinem µ^2, dieses µ entspricht hier dem Skalarprodukt aus bk(l-1) und bk(l-1)+1 korrekt!?
Vielleicht verstehe ich die Frage nicht, aber man berechnet sich natürlich immer nur das, was man braucht.
4. Für die Größenreduzierung brauchen wir wieder Die µs, diesmal aber von der gesamten Basis, da wir global vorgehen sollen!? Kann man die Werte irgendwie "einfach" updaten, denn sie stehen ja schon im Ergebnis der ComputeGS Funktion. Oder muss man sie jedes mal neu berechnen, wenn man zwei Segmente bearbeitet hat und diese zurück in die Basis B geschrieben hat? Laut dem Gitter.pdf Seite 35 ist die Längenreduktion in der For-Schleife berechenbar, die dort steht. Aber welche µs nimmt man? Die "aktualisierten" aus der darüberstehenden Berechnung? Oder werden die µ-Werte bereits durch den hinteren Teil der For-Schleife aktualisiert?
Ihr sollt global vorgehen, das ist richtig. Genau müsst ihr das aber nochmal nachlesen. Ggf. ist damit auch "globale" Reduktion auf einem 2k x 2k Block gemeint. Sollte im Paper stehen. Längenreduktion steht auf Seite 12, inklusive Korrektheitsbeweis.
Die angesprochenen Optimierungsvorschläge sollt ihr untereinander diskutieren.

Re: Segment-LLL Verständnisfragen

Verfasst: 2. Jun 2008 17:45
von Cyrtox
1. Beim letzten Treffen haben wir ja "festgestellt", dass sämtliche Matrizen quasi transponiert gespeiechert werden. Übrigens toll, dass die Ausgabefunktion über cout die Matrix trotzdem andersherum ausgibt und man sie sich dadurch immer transponiert vorstellen muss. Dadurch drehen sich auch SÄMTLICHE Operationen wie Matrixmultiplikationen um, oder? Sprich wenn ich beide Segmente * H rechnen muss, dann rechne ich im Code H * beide Segmente, wenn ich die Determinante ausrechne rechne ich Segment * Segment^T anstatt Segment^T * Segment usw. Ich hoffe das ist richtig, denn schon so richtet es ganz schön Verwirrung an!
Die NTL speichert alle Matrizen in Zeilenschreibweise. Dementsprechend müssen auch alle Basiswechsel auf Zeilen ausgeführt werden.
d.h. nehme ich mal an, dass ich richtig liege und sich alles umdreht? Naja hoffen wirs mal, nicht, dass wieder irgendwie nen Fehler durch sowas reinkommt.
2. Bei der Segment-LLL Abfrage ob ein Segment zurück oder eins weiter gesprungen werden soll braucht man die Determinanten beider Segmente. Ich habe bisher einfach ein einzelnes Segment extrahiert, es transponiert und dann B(l-1)^T * B(l-1) gerechnet, aus der resultierenden Matrix die Determinante und daraus die Wurzel. Das Ergebnis habe ich als Determinante des Segments l-1 genommen. Ist das so richtig? Ich habe noch eine andere Methode zur Berechnung der Determinante gesehen und zwar das aufmultiplizieren der Längenquadrate des Segments. Ka was nun richtig ist oder ob beides Richtig ist. Die Längenquadrate müsste man halt extra berechnen, was man ansonsten ja nicht machen muss.
Steht im Schnorr Skript. Die Determinante ist eindeutig und kann sicher auf verschiedene Weisen berechnet werden.
Stimmt es denn so wie ich es gemacht habe oder nicht? Naja werde nochmal im Skript wühlen, weiss bei dem Skript halt oft nicht welche Berechnung sich nun auf was bezieht und für welchen Fall man sie nun benutzen kann und für welchen nicht.
3. Wieder bei der Abfrage aus 2., hier braucht man auch noch die Längenquadrate des ersten Vektors des Segments l-1 sowie des 2. Vektors aus dem selben Segment. Wie berechnet man diese? Muss man dazu die Längenquadrate aller Vektoren der Basis berechnen? Oder reicht es direkt im Segment l-1 zu beginnen? Ich nehme an, denn wir rechnen ja mit den beiden Segmenten bzw dem TEIL der R Matrix, der diese beiden Segmente betrifft und nicht mit der ganzen Basis. Es würden wohl andere Werte dabei herauskommen... denn rechnet man nur in l-1, dann wäre das erste Längenquadrat ja einfach das Skalarprodukt von bk(l-1) mit sich selbst!? Und das 2. wäre das Skalarprodukt von bk(l-1)+1 mit sich selbst und davon das erste Längenquadrat multipliziert mit irgendeinem µ^2, dieses µ entspricht hier dem Skalarprodukt aus bk(l-1) und bk(l-1)+1 korrekt!?
Vielleicht verstehe ich die Frage nicht, aber man berechnet sich natürlich immer nur das, was man braucht.
Ähm ja klar berechnet man "nur" das, aber für das Längenquadrat des einen Vektors braucht man ja das des anderen usw... Aber mit welchen Werten rechnen wir denn nun? Ist bk(l-1) nun das ERSTE Längenquadrat (weil wir nur die 2 Segmente betrachten?), also nur ein Skalarprodukt, oder brauche ich doch aus der B Matrix alle vorangegangenen? Bzw eigentlich rechnen wir ja sogar mit Rl als Input von LLL, müssen wir dann die µ Werte der veränderten Rl Matrix nehmen oder doch die der Segmente.... ok nun bin ich vollends verwirrt.
4. Für die Größenreduzierung brauchen wir wieder Die µs, diesmal aber von der gesamten Basis, da wir global vorgehen sollen!? Kann man die Werte irgendwie "einfach" updaten, denn sie stehen ja schon im Ergebnis der ComputeGS Funktion. Oder muss man sie jedes mal neu berechnen, wenn man zwei Segmente bearbeitet hat und diese zurück in die Basis B geschrieben hat? Laut dem Gitter.pdf Seite 35 ist die Längenreduktion in der For-Schleife berechenbar, die dort steht. Aber welche µs nimmt man? Die "aktualisierten" aus der darüberstehenden Berechnung? Oder werden die µ-Werte bereits durch den hinteren Teil der For-Schleife aktualisiert?
Ihr sollt global vorgehen, das ist richtig. Genau müsst ihr das aber nochmal nachlesen. Ggf. ist damit auch "globale" Reduktion auf einem 2k x 2k Block gemeint. Sollte im Paper stehen. Längenreduktion steht auf Seite 12, inklusive Korrektheitsbeweis.
Die angesprochenen Optimierungsvorschläge sollt ihr untereinander diskutieren.
Auf einem 2k x 2k Block !? Wie soll das denn gehen, die Segmente sind ja nichtmal 2k x 2k!

Re: Segment-LLL Verständnisfragen

Verfasst: 5. Jun 2008 14:46
von Cyrtox
Also wir haben unseren Fehler bei ComputeGS gefunden, die QR Zerlegung funktioniert nun endlich einwandfrei!
Wir hatten den Rest ja ohnehin schon "blind" gecoded und haben nun besser testen können, ob es funktioniert. Es läuft nun (oft) durch, jedenfalls wenn ich vor dem Basis return das Programm beende. Die Ergebnisse sehen ganz gut aus, die Frage ist nun allerdings ist es eine korrekte LLL reduzierte Basis oder nicht!? Die HNF ist die selbe wie von B zu Beginn und die einzelnen Zeilen (im Code, also Spalten in Wirklichkeit) scheinen von der Länge her kleiner zu sein als die in B, jedenfalls sah es bisher so aus. Abgesehen von dem Problem "Wie stellt man fest ob das Ergebnis korrekt ist?" haben wir noch ein anderes, größeres Problem. Ich sagte ja bereits, dass es oft durchläuft. Aber eben auch öfter nicht. Der Grund ist, dass bei der Transformationsmatrix H (aus dem LLL über die Matrix Rl) oft die Einheitsmatrix herauskommt. Sobald dies passiert geht der Algo natürlich in eine Endlosschleife. Wie kommt sowas zustande? Jemand eine Idee?

Re: Segment-LLL Verständnisfragen

Verfasst: 10. Jun 2008 11:19
von Cyrtox
Haben nun die Aktualisierung der µ-Werte mit aufgenommen und es hat nichts verändert. Es war so, wie ichs mir bereits gedacht hatte, jeder µ-Wert wird innerhalb eines Reduce-Aufrufs nur einmal verwendet und vor einem erneuten Reduce-Aufruf wird ohnehin ComputeGS erneut aufgerufen. Schade... es sah so sehr nach dem Fehler aus.