L2 Reduction: LLL Algorithm With Quadratic Complexity

This is part of our series on LLL where we’ve coded

1. Original 1982 LLL Reduction paper.
2. Lattice reduction in 2-Dimensions.
3. Gaussian lattice sieving .
4. LLL Applied to Hermite Normal Forms and GCD.
5. (we are here): L2 reduction, Floating-Point LLL Reduction With Quadratic Complexity.Subscribe to receive weekly paper implementations.

1.0 Paper Introduction

An LLL Algorithm With Quadratic Complexity (Nguyen & Stehle, 2009)1 introduces a floating-point variation of LLL reduction with quadratic, not cubic complexity.

This quadratic-complexity LLL variant is proven to terminate and is described as a generalization of the 2D Gauss-Lagrange reduction (Nguyen & Stehle, 2009).

The authors improve on the original LLL by:

1. Using an exact initial Gram matrix to improve accuracy of Gram-Schmidt orthogonalization (GSO). This is the matrix G=(BTB) where B is the input basis.
   • If B is a basis with these column vectors:
   • Then the corresponding Gram matrix is:
2. Adapting Babai’s nearest plane algorithm to floating-point arithmetic to stabilize size reduction.

(Nguyen & Stehle, 2009) introduce a new size reduction where reduction happens progressively, not all at once.

This new reduction doesn’t require high floating-point accuracy but requires more steps to achieve. Overall, it’s less expensive as it eliminates exact rational arithmetic of the GSO.

We provide the new size-reduction algorithm below:

2.0 Coding L2

Code is available on GitHub. We code an RNG to make our results reproducible across different languages.

In Python, the RNG resembles:

import numpy as np
import math

def NextRandLCG(state):
    state[0] = (1664525 * state[0] + 1013904223) & 0xFFFFFFFF
    return state[0]

def Matrix_Index2D(i, j, cols):
    return i * cols + j

def RandomMatrixLCG(rows, cols, seed, low, high):
    out = np.empty(rows * cols, dtype=np.int32)
    for i in range(rows):
        for j in range(cols):
            idx = Matrix_Index2D(i, j, cols)
            out[idx] = low + (NextRandLCG(seed) % (high - low + 1))
    return out.reshape(rows, cols)

The L2 algorithm is proven to terminate and is given below:

2.1 Gram Matrix

The Gram Matrix is the set of all possible inner products (Weisstein, 2026)2. It is found by:

Python code to find the Gram matrix resembles:

def FindGramMatrix(basis):
    d, n = B.shape
    G = np.zeros((n, n), dtype=object)
    for j in range(n):
        for i in range(j + 1):
            s = sum(B[l, j] * B[l, i] for l in range(d))
            G[j, i] = G[i, j] = s
    return G

2.2 Initialize Helper Matrices

We init these matrices similar to typical LLL:

A Python function to init and return the largest gram-schmidt coefficient resembles:

def Init_SquareAndCoeffs(squareNorm, gramCoefficients, colIndex, G):
    for i in range(colIndex + 1):
        squareNorm[i, colIndex] = float(G[i, colIndex])
        for j in range(i):
            squareNorm[i, colIndex] -= squareNorm[j, colIndex] * gramCoefficients[j, i]
        gramCoefficients[i, colIndex] = squareNorm[i, colIndex] / squareNorm[i, i]
    largestCoeff = max(abs(gramCoefficients[j, colIndex]) for j in range(colIndex))
    return largestCoeff

*Note that LLL demands a full-rank matrix. A computational trick for this constraint is to ensure the number of rows is greater or equal to the number of cols.

2.3 Reduction Function

The reduction function works on a basis vector (each column) like this:

For each previous basis column:

1. Find the nearest integer to the Gram-Schmidt coefficient.
2. Stop if X is zero.
3. If X is not zero:
   1. Update the current column:
   2. Update the gram matrix dot products to reflect the basis change.
   3. Update affected gram coefficients.

Python code for the reduction step resembles:

def PerformSizeReduction(colIndex, rows, cols, gramCoefficients, gramMatrix, basis):
    for j in range(colIndex - 1, -1, -1):
        #Find closest integer 
        X = math.floor(float(gramCoefficients[j, colIndex]) + 0.5)
        if X != 0:
            #Update basis
            for i in range(rows):
                basis[i, colIndex] -= X * basis[i, j]
            #Update gram matrix
            for i in range(cols):
                dot = sum(basis[l, i] * basis[l, colIndex] for l in range(rows))
                gramMatrix[colIndex, i] = gramMatrix[i, colIndex] = dot
            #Update gram coefficients
            for i in range(j):
                gramCoefficients[i, colIndex] -= X * gramCoefficients[i, j]   

Note that size reduction is triggered unconditionally in original LLL.

L2 size reduction happens only when a coefficient in the current column is larger than expected.

2.4 Lovasz Condition Check

Original LLL tracks the Lovasz condition to ensure norms don’t fall fast. L2 has a variant of this condition and the check is triggered if reduction in step 2.3 did not happen.

We define the familiar LLL constants, delta and dd:

delta = 0.99
dd = (delta + 1.0) / 2.0
------ other l2 code ------ 

If the Lovasz test passes then we move to the next column:

if dd * squareNorm[currentCol-1, currentCol-1] < squareNorm[currentCol, currentCol] + gramCoefficients[currentCol-1, currentCol]**2 * squareNorm[currentCol-1, currentCol-1]:
     currentCol += 1
else:
     #Handle case lovasz failed

If it fails then we swap adjacent columns, recompute Gram Schmidt information and decrease the current column by 1:

Python code resembles:

else:
#Swap columns
B[:, [currentCol-1, currentCol]] = B[:, [currentCol, currentCol-1]]
#Recompute Gram schmidt values after swap
for m in [currentCol-1, currentCol]:
    for i in range(cols):
        dot = sum(B[l, i] * B[l, m] for l in range(rows))
        G[m, i] = G[i, m] = dot

for col in [currentCol-1, currentCol]:
    for i in range(col + 1):
        squareNorm[i, col] = float(G[i, col])
        for j in range(i):
            squareNorm[i, col] -= squareNorm[j, col] * gramCoefficients[j, i]
        gramCoefficients[i, col] = squareNorm[i, col] / squareNorm[i, i]
#Decrease to previous column
currentCol -= 1
if currentCol < 1:
    currentCol = 1

2.5 Tying Everything Together

(Stehle, 2009)3 demonstrates how everything works in place. Python code resembles:

We can test it on a basis and compare the norm before and after reduction:

It works!

Subscribe if you made it this far

3.0 Bonus Content

3.1 Precomputing the Gram Matrix

Say you desire to draw your basis vectors from a fixed set. For instance, suppose you have 5 possible column vector in R3:

Say you desire to sample only 3 basis vectors at a time. For instance, your sampler may choose:

Your code would calculate:

Observe that we can precompute the entire Gram matrix and index to generate our desired subset:

That is, our sublattice spans:

and the indexed Gram matrix is:

3.2 Changing Final Vector

Gram-Schmidt is sequential. We can save computations by swapping out the final vector at every sampling stage. Swapping out the first vector is profoundly expensive.

Say we LLL reduced the basis:

Matrix uu and rr resemble:

Then we swap the final column vector to obtain:

Our new uu and rr resemble:

Observe that only the final column changes.

Subscribe now

References

1

Nguyen, P. Q., & Stehlé, D. (2009). An LLL Algorithm With Quadratic Complexity. SIAM Journal on Computing, 39(3), 874–903. https://doi.org/10.1137/070705702

2

Weisstein, E. W. (n.d.). Gram Matrix. MathWorld—A Wolfram Web Resource. https://mathworld.wolfram.com/GramMatrix.html

3

Stehlé, D. (2009). Floating-Point LLL: Theoretical and Practical Aspects. In: Nguyen, P., Vallée, B. (eds) The LLL Algorithm. Information Security and Cryptography. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02295-1_5