LLL Algorithm — Lenstra–Lenstra–Lovász Lattice Reduction

The LLL algorithm, introduced by Arjen Lenstra, Hendrik Lenstra, and László Lovász in their 1982 paper Factoring polynomials with rational arithmetic, was the first polynomial-time algorithm for finding a provably short vector in an arbitrary lattice. Its primary motivation was polynomial factorization, but it immediately found applications in breaking the Merkle–Hellman knapsack cryptosystem, solving integer programs in fixed dimension, and Diophantine approximation. Before LLL, lattice reduction was an open problem. After LLL, it became the workhorse of lattice cryptanalysis — and remains so today.

Beginner's Intuition 💡

Imagine you are given a tangled, terribly confusing set of directions to walk around a city (a "bad basis"). The LLL Algorithm is like a smart GPS that systematically untangles these directions.

It looks at your path just two steps at a time, constantly asking: "Can I take a shortcut here instead of walking the long way around?" By repeatedly smoothing out these small sections, it magically transforms a chaotic path into a surprisingly efficient and direct route. While it doesn't give you the absolute shortest path possible, it gets you very close, incredibly quickly!

Gram–Schmidt Orthogonalization

LLL is built on the Gram–Schmidt orthogonalization of the basis. Given basis vectors $b_{1}, \dots, b_{n}$ , define the Gram–Schmidt vectors $b_{1}^{*}, \dots, b_{n}^{*}$ by:

b_{i}^{*} = b_{i} - j = 1 \sum i - 1 μ_{i, j} b_{j}^{*}

where the Gram–Schmidt coefficients are:

μ_{i, j} = \frac{⟨ b _{i} , b _{j}^{*} ⟩}{⟨ b _{j}^{*} , b _{j}^{*} ⟩}

The Gram–Schmidt vectors are orthogonal but not in the lattice — they live in the real span. Their norms $∥ b_{i}^{*} ∥$ measure how much each basis vector contributes beyond the previous ones. A reduced basis has Gram–Schmidt vectors of roughly comparable length.

LLL Reduction Conditions

A basis $B = [b_{1} ∣ \dots ∣ b_{n}]$ is LLL-reduced with parameter $δ \in (1/4, 1)$ if it satisfies two conditions:

Size reduction — all off-diagonal Gram–Schmidt coefficients are small:

∣ μ_{i, j} ∣ \leq \frac{1}{2} for all 1 \leq j < i \leq n

Lovász condition — consecutive Gram–Schmidt vectors do not decrease too fast:

δ ∥ b_{i - 1}^{*} ∥^{2} \leq ∥ b_{i}^{*} ∥^{2} + μ_{i, i - 1}^{2} ∥ b_{i - 1}^{*} ∥^{2} for all i

The standard choice is $δ = 3/4$ . When $δ$ is closer to 1, the output is better but the algorithm takes more iterations. When $δ = 1$ , the problem becomes NP-hard (it is equivalent to SVP).

The Algorithm

LLL interleaves two operations: size-reduce each vector against all previous ones, then check the Lovász condition and swap adjacent vectors if it fails.

Input: basis $B = (b_{1}, \dots, b_{n})$ , parameter $δ \in (1/4, 1)$
Output: LLL-reduced basis

1. Compute Gram–Schmidt orthogonalization of $B$ .
2. Set $k = 2$ .
3. Size-reduce $b_{k}$ : for $j = k - 1$ down to $1$ , set $b_{k} \leftarrow b_{k} - ⌊ μ_{k, j} ⌉ b_{j}$ and update Gram–Schmidt.
4. If Lovász condition holds at $k$ , increment $k \leftarrow k + 1$ .
5. Otherwise swap $b_{k - 1}$ and $b_{k}$ , update Gram–Schmidt, set $k \leftarrow max (k - 1, 2)$ .
6. Repeat from step 3 until $k > n$ .

Output Quality

The first vector $b_{1}$ of an LLL-reduced basis satisfies:

∥ b_{1} ∥ \leq (\frac{2}{4 δ - 1})^{n - 1} \cdot λ_{1} (Λ)

For $δ = 3/4$ this gives an approximation factor of $2^{(n - 1) /2}$ . In practice LLL performs far better than this worst-case bound — experimentally the output is roughly $1.0 2^{n} \cdot λ_{1}$ .

Complexity

LLL runs in polynomial time. For an $n$ -dimensional lattice with basis vectors of bit-length at most $B$ :

O (n^{6} B^{2})

bit operations. The number of swap steps is bounded by $O (n^{2} lo g B)$ . This polynomial bound — compared to the exponential time needed for exact SVP — is what makes LLL so powerful.

Cryptographic Impact

In its original 1982 paper, LLL was applied to break the Merkle–Hellman knapsack cryptosystem, which had been considered secure for five years. The attack reduced the problem to finding a short vector in a carefully constructed lattice and ran in minutes on a computer.

LLL is a subroutine inside every stronger lattice reduction algorithm (BKZ, HKZ). It is also used in attacks on poorly parameterized RSA (Coppersmith's method uses LLL to find small roots of polynomials), in breaking ECDSA when nonces are biased, and in solving the hidden number problem.

For lattice-based cryptography like Kyber and Dilithium, the parameters are chosen precisely so that LLL alone is far too weak — but it remains the essential building block of every known attack.

LLL Variants: Complexity Comparison

Several improved variants of LLL have been developed, trading implementation complexity for better practical performance. The table below summarizes the main variants by their theoretical complexity and practical approximation quality.

LLL ( $δ = 3/4$ ): original algorithm. Bit complexity $O (n^{6} B^{2})$ . Approximation factor $2^{(n - 1) /2}$ worst case.

L² algorithm (Nguyen–Stehlé, 2005): floating-point LLL with rigorous error control. Runs in $O (n^{5} (n + B) B)$ bit operations — strictly better than classical LLL. Achieves the same output quality guarantee but is the standard in all modern implementations. The key insight is to use a fixed-precision floating-point arithmetic model with carefully chosen precision $η \geq n + lo g_{2} B$ bits, re-establishing exactness guarantees without symbolic arithmetic.

Deep insertions LLL (Schnorr–Euchner, 1994): instead of only swapping adjacent vectors, inserts $b_{k}$ at the earliest position where it would satisfy the Lovász condition. Produces better bases in practice but the termination proof requires a different potential function and the worst-case complexity is $O (n^{8} B^{2})$ .

BKZ-2 (Chen–Nguyen, 2011): with block size $β = 2$ , BKZ reduces to LLL with deep insertions. Block size is the parameter controlling the transition from polynomial (LLL) to exponential (BKZ) complexity.

Python Implementation from Scratch

The following is a complete, self-contained Python implementation of the LLL algorithm. It uses only NumPy and follows the mathematical description above step by step: Gram–Schmidt orthogonalization, size reduction, and the Lovász swap condition.

import numpy as np

def gram_schmidt(B):
    """
    Compute Gram-Schmidt orthogonalization.

    Returns:
        B_star: orthogonal vectors (same shape as B)
        mu: matrix of Gram-Schmidt coefficients
             mu[i,j] = <b_i, b*_j> / <b*_j, b*_j>
    """
    n = B.shape[0]
    B_star = np.zeros_like(B, dtype=float)
    mu = np.zeros((n, n), dtype=float)

    for i in range(n):
        B_star[i] = B[i].copy()
        for j in range(i):
            # project b_i onto each previous orthogonal vector b*_j
            mu[i, j] = np.dot(B[i], B_star[j]) / np.dot(B_star[j], B_star[j])
            B_star[i] -= mu[i, j] * B_star[j]

    return B_star, mu


def lll_reduction(B, delta=0.75):
    """
    LLL lattice basis reduction.

    Args:
        B: integer matrix where rows are basis vectors (n x m)
        delta: reduction parameter in (0.25, 1). Default 0.75.
               Higher delta → better output but more iterations.

    Returns:
        B: LLL-reduced basis (modified in place)
    """
    B = np.array(B, dtype=float)
    n = B.shape[0]
    B_star, mu = gram_schmidt(B)

    k = 1
    while k < n:
        # === Step 1: Size reduction ===
        # Make |mu[k,j]| <= 0.5 for all j < k
        # This ensures basis vectors are not too skewed
        for j in range(k - 1, -1, -1):
            if abs(mu[k, j]) > 0.5:
                # Subtract the nearest integer multiple of b_j from b_k
                q = round(mu[k, j])
                B[k] -= q * B[j]
                # Update Gram-Schmidt coefficients
                B_star, mu = gram_schmidt(B)

        # === Step 2: Lovász condition ===
        # Check: delta * ||b*_{k-1}||^2 <= ||b*_k||^2 + mu[k,k-1]^2 * ||b*_{k-1}||^2
        # This prevents Gram-Schmidt norms from dropping too fast
        norm_k = np.dot(B_star[k], B_star[k])
        norm_k1 = np.dot(B_star[k - 1], B_star[k - 1])
        lovasz = norm_k + mu[k, k - 1] ** 2 * norm_k1

        if lovasz >= delta * norm_k1:
            # Condition satisfied → move to next index
            k += 1
        else:
            # Condition violated → swap b_k and b_{k-1}
            B[[k, k - 1]] = B[[k - 1, k]]
            B_star, mu = gram_schmidt(B)
            # Step back (but not below index 1)
            k = max(k - 1, 1)

    return B


# === Example usage ===
# Create a "bad" 4-dimensional basis with nearly parallel vectors
basis = np.array([
    [1,  1,  1,  1],
    [-1, 0,  0,  0],
    [3,  5,  6,  6],
    [1,  2,  3,  7],
])

print("Original basis:")
print(basis)
print("Norms:", [round(np.linalg.norm(row), 2) for row in basis])

reduced = lll_reduction(basis, delta=0.75)
print("\nLLL-reduced basis:")
print(reduced.astype(int))
print("Norms:", [round(np.linalg.norm(row), 2) for row in reduced])

How this works step by step:

1. Gram–Schmidt orthogonalization decomposes each basis vector into a component orthogonal to all previous vectors ( $b_{i}^{*}$ ) plus projections onto them ( $μ_{i, j}$ coefficients). The orthogonal components reveal the "true" contribution of each vector.

2. Size reduction ensures $∣ μ_{k, j} ∣ \leq 1/2$ by subtracting integer multiples of earlier basis vectors. This is the lattice analogue of reducing off-diagonal entries in row echelon form — except we round to the nearest integer to stay in the lattice.

3. The Lovász condition checks that consecutive Gram–Schmidt norms do not drop too sharply. When violated, the algorithm swaps the two vectors. This swap strictly decreases a potential function $\prod_{i} ∥ b_{i}^{*} ∥^{2 (n - i)}$ , guaranteeing termination in polynomial time.

4. The index $k$ moves forward when the Lovász condition holds and steps back after a swap, ensuring no earlier violations are introduced.

Note: This implementation recomputes Gram–Schmidt from scratch after each update for clarity. Production implementations (like FPLLL) use incremental updates, which reduces the per-iteration cost from $O (n^{2})$ to $O (n)$ .

LLL in Practice: FPLLL

The standard implementation of LLL (and BKZ) is FPLLL (Floating-Point LLL), an open-source C++ library maintained by the lattice cryptography community. It implements the L² algorithm, BKZ 2.0 with pruned enumeration, and the g6k sieve interface.

A minimal FPLLL session in Python via the fpylll wrapper:

from fpylll import IntegerMatrix, LLL

# create a random 40-dimensional lattice basis
A = IntegerMatrix.random(40, "qary", k=20, bits=30)

# run LLL with delta = 0.99
LLL.reduction(A, delta=0.99)

# inspect first basis vector length
print(A[0].norm())

Typical input/output: a 100-dimensional basis with entries of ~100 bits. LLL reduces it in under one second on a modern CPU. The first vector of the output is typically around $1.0 2^{100}$ times the lattice minimum — roughly 7× the theoretical minimum, but far shorter than a random basis vector (which would be exponentially longer). For an $n$ -dimensional lattice arising from an RSA modulus, this translates directly into small-root-finding capability via Coppersmith's method.

Floating-point precision: the L² algorithm uses double precision ( $\approx 53$ bits) for small dimensions and switches to arbitrary-precision arithmetic (via MPFR) when the basis coefficients grow large. FPLLL handles this transition automatically, controlled by the float_type parameter ("double", "long double", "dpe", "mpfr"). For dimensions above ~170 or basis bitlength above ~500, double precision accumulates enough rounding error to produce incorrect Gram–Schmidt coefficients, and MPFR is required.