Implementierung von LLL-Algorithmus wie auf Wikipedia gesagt, aber in ernsthafte Probleme geraten
Ich bin mir nicht sicher, ob mein Problem mit der Programmierung oder dem Konzept des LLL-Algorithmus zusammenhängt und was auf Wikipedia erwähnt wurde.
Ich habe beschlossen, den LLL-Algorithmus so zu implementieren, wie er auf Wikipedia (Schritt-für-Schritt / Zeile-für-Zeile) , um den Algorithmus zu lernen und sicherzustellen, dass er wirklich funktioniert, aber ich unerwartete oder ungültige Ergebnisse erhalte.
Also habe ich JavaScript (Programmiersprache) und node.js (JavaScript Engine) verwendet, um es zu implementieren und das ist das Git-Repository um den vollständigen Code zu erhalten.
Lange Rede, kurzer Sinn, der Wert von K gerät außer Reichweite, zum Beispiel wenn wir nur 3 Vektoren haben (die Array-Größe ist 3, der Maximalwert des Index wäre also 2), aber k wird 3 und ist Unsinn.
Mein Code ist eine Schritt-für-Schritt-Implementierung des Algorithmus, der auf Wikipedia und was ich getan habe, war es nur zu implementieren. Also ich nicht was ist das Problem.
%Vor%Hier ist der Screenshot des Algorithmus auf Wikipedia:
Update # 1 : Ich habe dem Code weitere Kommentare hinzugefügt, um die Frage zu klären, in der Hoffnung, dass jemand helfen würde.
Falls Sie sich über die bereits verfügbare Implementierung des Codes wundern, können Sie Folgendes eingeben: LatticeReduce[{{0,1},{2,0}}] wolfram alpha um zu sehen, wie sich dieser Code verhalten soll.
Update # 2 : Ich habe den Code aufgeräumt und eine Validierungsfunktion hinzugefügt, damit der Code von Gram Schmidt korrekt funktioniert, aber der Code schlägt fehl und der Wert von k überschreitet die Anzahl der Dimensionen (oder die Anzahl von Vektoren), die keinen Sinn ergeben.
1 Antwort
Die Algorithmusbeschreibung in Wikipedia verwendet eher eine ungerade Schreibweise - die Vektoren sind mit 0..n nummeriert (statt etwa 0..n-1 oder 1..n), so dass die Gesamtzahl der Vektoren n + ist 1.
Der Code, den Sie hier gepostet haben, behandelt this.dimensions so, als ob er n in der Beschreibung von Wikipedia entspricht. Daran ist bisher nichts falsch.
Der Konstruktor in der vollständigen Quelldatei von GitHub setzt jedoch this.dimensions = matrix[0].length . Zwei Dinge daran scheinen falsch. Der erste ist, dass matrix[0].length eher m (die Dimension des Raums) ist als n (die Anzahl der Vektoren, minus 1 aus unklaren Gründen). Die zweite ist, dass, wenn es n sein soll, Sie 1 subtrahieren müssen, weil die Anzahl der Vektoren n + 1 ist, nicht n.
Wenn Sie also this.dimensions für n verwenden wollen, müssen Sie es als matrix.length-1 initialisieren. Mit der quadratischen Matrix in Ihrem Testfall würde die Verwendung von matrix[0].length-1 funktionieren, aber ich denke, dass der Code dann bricht, wenn Sie eine nicht-quadratische Matrix einspeisen. Der Name dimensions ist auch irgendwie irreführend; vielleicht nur n , um mit der Beschreibung der Wikipedia übereinzustimmen?
Oder Sie könnten es so nennen wie nVectors , lassen Sie es gleich matrix.length und ändern Sie den Rest des Codes entsprechend, was nur eine Anpassung in der Abbruchbedingung für die Hauptschleife bedeutet.
Tags und Links javascript algorithm node.js cryptography ecmascript-6