THE GARDEN

LLL Algorithm (Lattice Basis Reduction)

Updated 13 Sep 2026

• •

  What it is

  • •

    A lattice is the set of all integer linear combinations of a set of basis vectors — think of it as an infinite, regularly-spaced grid of points in space, generalizing the integers themselves to multiple dimensions. The same lattice can be described by many different bases, some far more useful than others: a "reduced" basis has short, close-to-orthogonal vectors, while an arbitrary basis for the same lattice can have long, heavily-skewed ones that hide the lattice's actual structure. The LLL algorithm (Lenstra-Lenstra-Lovász) efficiently transforms any given basis into a reduced one in polynomial time, guaranteeing the first vector it produces is provably not too much longer than the lattice's true shortest vector. This matters enormously in cryptanalysis because many hard problems — hidden linear relationships, RSA private-key bounds, structured "almost-solutions" to polynomial equations — can be reframed as "find an unusually short vector in this specially-constructed lattice," at which point LLL just solves them directly.

• •

  When to apply

  • •

    A problem can be reframed as finding small/short integer values satisfying a linear (or, via Coppersmith's extension, certain polynomial) relationship, where you can construct a lattice basis encoding that relationship — the general "smallness implies findable by LLL" pattern shows up throughout the RSA and knapsack attacks in this graph.

• •

  Symbols and assumptions

  • •

    A lattice basis $b_1,\ldots,b_n$ spans integer combinations $\sum z_i b_i$. Gram–Schmidt vectors $b_i^*$ are orthogonal real/rational guides; $\mu_{ij}$ are projection coefficients. LLL changes the integer basis, not the lattice.

• •

  Math — step by step

  • •
    1. Size reduction replaces $b_i$ by $b_i-\lfloor\mu_{ij}\rceil b_j$. The multiplier is an integer, so the generated lattice is unchanged.
  • •
    2. Check the Lovász condition $\|b_i^*\|^2\ge(\delta-\mu_{i,i-1}^2)\|b_{i-1}^*\|^2$ with $1/4<\delta<1$. If it fails, swap neighboring vectors and recompute.
  • •
    3. Continue until the basis is size-reduced and passes the condition. LLL produces a provably reduced basis, not necessarily the shortest vector or the desired secret.
  • •
    4. A cryptanalytic use still needs an embedding that makes a true solution short and a verification step translating candidates back to the original equations.
• •

  Worked example

  • •

    Take $b_1=(1,1)$ and $b_2=(100,101)$. The projection coefficient is $\mu=(100+101)/(1+1)=100.5$. Choose the nearest integer 100.

  • •

    Size-reduce: $b_2-100b_1=(0,1)$. This much shorter vector was already in the same lattice.

  • •

    For these two vectors, $b_2^*=(-1/2,1/2)$ has squared norm $1/2$. With $\delta=3/4$ and $\mu=1/2$, the Lovász bound is $(3/4-1/4)\cdot2=1$, so a swap is required.

  • •

    After swapping, reduce $(1,1)$ by $(0,1)$ to obtain $(1,0)$. The new basis $(0,1),(1,0)$ spans exactly the same integer grid.

• •

  Python

  • •

    from fractions import Fraction as F
    def dot(u, v): return sum(F(a)*F(b) for a,b in zip(u,v))
    def gram_schmidt(B):
            Bstar, mu = [], [[F(0)]*len(B) for _ in B]
            for i, bi in enumerate(B):
                v = [F(x) for x in bi]
                for j in range(i):
                    mu[i][j] = dot(bi, Bstar[j]) / dot(Bstar[j], Bstar[j])
                    v = [v[k] - mu[i][j]*Bstar[j][k] for k in range(len(bi))]
                Bstar.append(v)
            return Bstar, mu
    def lll(B, delta=F(99,100)):
            B = [row[:] for row in B]; n = len(B)
            Bstar, mu = gram_schmidt(B); k = 1
            while k < n:
                for j in range(k-1, -1, -1):
                    q = round(mu[k][j])
                    if q: B[k] = [B[k][t]-q*B[j][t] for t in range(len(B[k]))]; Bstar, mu = gram_schmidt(B)
                if dot(Bstar[k],Bstar[k]) >= (delta-mu[k][k-1]**2)*dot(Bstar[k-1],Bstar[k-1]):
                    k += 1
                else:
                    B[k], B[k-1] = B[k-1], B[k]; Bstar, mu = gram_schmidt(B); k = max(k-1,1)
            return B
    

• •

  SageMath

  • •

    Sage's Matrix.LLL() (backed by the industrial-strength fpLLL library) is dramatically faster and more numerically robust than any hand-rolled version — the practical tool of choice for anything beyond small toy lattices:

  • •

    M = Matrix(ZZ, rows)
    reduced = M.LLL()
    

• •

  Related

  • •

    Hidden Subset Sum - Knapsack Recovery via Lattice Reduction (LLL)

  • •

    Coppersmith's Method for Stereotyped-Partially-Known Messages

  • •

    Boneh-Durfee Attack (Lattice Attack on Small RSA Private Exponent)

  • •

    ROCA Vulnerability (Infineon RSA Key Generation Weakness)

• •

  Cards

  • •

    What does a "reduced" lattice basis mean, informally?

    • •

      Short, close-to-orthogonal vectors describing the same lattice as the original (possibly long, skewed) basis.

  • •

    What guarantee does LLL provide about the first vector of its output basis?

    • •

      It's provably within an exponential factor of the lattice's true shortest vector — not optimal, but efficiently computable and reliably short enough for most cryptanalytic uses.

◌ Explore connections in Graph view