LLL-Algorithmus

Ein polynomiellaufzeitliches Gitterbasis-Reduktionsverfahren, das zu einer Basis eines Gitters im euklidischen Raum eine reduzierte Basis aus relativ kurzen, annähernd orthogonalen Vektoren ausgibt, welche Size-Reduction-Schritte und die Lovász-Bedingung für einen gewählten Parameter δ∈(1/4,1] erfüllen.

Ein Algorithmus zur Gitterreduktion in Polynomialzeit, der zu einer gegebenen Basis eines euklidischen Gitters eine reduzierte Basis liefert, deren Vektoren relativ kurz und nach der Lovász-Bedingung nahezu orthogonal sind; vielfach eingesetzt in algorithmischer Zahlentheorie, Algebra und Kryptanalyse.