LLL Lattice Reduction

Picture an infinite grid of points scattered across the plane in a perfectly regular pattern — a lattice. You can generate every single point by adding whole-number combinations of just two vectors, its basis. The catch: the same lattice has infinitely many valid bases. Some are short and almost perpendicular, like a neat pair of rulers. Others are long, nearly parallel, and practically useless for reading off where the points sit.

Given a bad, skewed basis, can you find a good one — short vectors, close to a right angle — without changing the lattice itself? In two or three dimensions you could eyeball it. In twenty, or two hundred, dimensions there is no eyeballing anything, and the number of equally valid bases explodes.

In 1982, Arjen Lenstra, Hendrik Lenstra, and László Lovász published an algorithm — now simply called LLL — that solves this cleanly: it always terminates in polynomial time and always hands back a basis that is provably short and provably close to orthogonal. It doesn't find the single best basis possible, but it gets close enough, fast enough, to be one of the most consequential algorithms in computational mathematics.

Below is a 2D lattice: every gray dot is reachable by combining two basis vectors, drawn as arrows from the origin. The starting basis is deliberately awful — long and almost parallel, so the arrows nearly overlap.

Click Step to watch one move of the algorithm at a time, or Reduce fully to jump straight to the finished basis. Either way, the same lattice of gray dots never moves — only the two arrows describing it change.

<p class="hint">{{hint_para}}</p>
<div class="controls">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="reduce" type="button">{{btn_reduce}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="info-bar">
  <span>{{label_len}}: <b id="lens">—</b></span>
  <span>{{label_angle}}: <b id="angle">—</b></span>
  <span>{{label_steps}}: <b id="steps">0</b></span>
</div>
<canvas id="cv" width="480" height="340"></canvas>
<div class="status" id="status">{{status_start}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: transparent; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.info-bar { display: flex; gap: 1.2rem; flex-wrap: wrap; font-size: .88rem; margin-bottom: .4rem; color: #444; }
.info-bar b { color: #1d3557; }
#cv { display: block; border: 1px solid #cdd9e3; border-radius: 8px; background: #f8fafc;
      max-width: 100%; height: auto; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0 0; min-height: 1.4em; color: #0a7d33; }
.status.done { color: #0a7d33; }

// Code not found

Watch the vector lengths and the angle between them in the readout. A skewed basis starts long with an angle near 0° or 180°; a reduced basis ends short with an angle close to 90°. LLL gets there using only two moves, repeated: subtract an integer multiple of one vector from the other, and swap the two vectors when that makes the pair shorter overall.

LLL is a solved algorithm — but it solves a deliberately weakened version of a much harder question.

• LLL itself is polynomial time. For a lattice basis in $n$ dimensions with integer entries of bit-length at most $b$, LLL terminates after $O(n^{4}\log b)$ arithmetic operations (the original 1982 bound, later improved), each on numbers of polynomially many bits. That is comfortably inside P.
• It only approximates the shortest vector. The true goal — find the single shortest non-zero point in the lattice, the Shortest Vector Problem (SVP) — is what LLL is standing in for. LLL guarantees a vector no more than roughly $2^{(n-1)/2}$ times longer than the true shortest one. For small $n$ that factor is negligible; for $n$ in the hundreds it is astronomically loose.
• Exact SVP is believed hard. Finding the exact shortest vector, or even a good constant-factor approximation of it, is NP-hard under randomized reductions in high dimension, and no polynomial-time algorithm is known for it in general.
• Stronger reduction narrows the gap, at a cost. Algorithms like BKZ trade running time for a better approximation factor than plain LLL, sliding along the same tradeoff curve rather than escaping it.

So the honest one-line status is: LLL, the algorithm, is solved and fast; SVP, the problem it approximates, is open and believed intractable in high dimension. That gap — small enough for LLL to demolish weak schemes, wide enough that no known algorithm closes it against well-parameterized ones — is exactly what modern lattice-based cryptography, including the Learning with Errors problem, is built to exploit. See also the related Shortest Vector Problem.

A fast subroutine that finds short vectors in a lattice turns out to be useful anywhere a hidden simple structure needs to be dug out of numbers that look unrelated:

• Integer-relation detection: given real numbers $x_1, \dots, x_n$, is there a nonzero set of integers $a_1, \dots, a_n$ with $a_1 x_1 + \cdots + a_n x_n = 0$? Feed the numbers into a lattice construction and let LLL (or its refinement, the PSLQ algorithm) find the short vector that encodes the relation. This is how mathematicians have discovered new identities among constants like $\pi$ and $\log 2$ purely by computer search.
• Cryptanalysis of weak schemes: LLL instantly broke the Merkle–Hellman knapsack cryptosystem the same year it was published, and Coppersmith's method (1996) uses LLL to recover small roots of polynomials modulo $N$ — a real attack on RSA when a key or message fragment is smaller than it should be.
• Fixed-dimension integer programming: Lenstra showed in 1983 that integer linear programs in a fixed number of variables can be solved in time polynomial in the rest of the input, using LLL to find short vectors inside the constraint lattice.
• Polynomial factorization: the original 1982 paper used lattice reduction to factor polynomials with rational coefficients in polynomial time — the problem the algorithm was actually designed to solve.
• Post-quantum benchmarking: LLL and stronger relatives like BKZ are the yardsticks cryptographers run against candidate parameters for schemes such as Kyber and Dilithium, to make sure no known reduction algorithm comes close to breaking them.

Very little in LLL's design mentions cryptography or number theory specifically — it is a general geometric hammer, and an enormous number of problems turn out to look like nails.

LLL never promises the single best basis for a lattice — only one that is provably good enough, delivered in polynomial time no matter how skewed the starting point was. That modest-sounding guarantee turned out to be sharp enough to shatter an entire generation of cryptosystems and versatile enough to help mathematicians discover identities no one had written down before.

The algorithm is not the open frontier here — it is a clean, closed chapter from 1982. The open frontier is the problem it only approximates: the exact Shortest Vector Problem, believed intractable in high dimension, and now one of the load-bearing walls of post-quantum cryptography.

Next time a mess of numbers looks tangled beyond hope, remember that "good enough, fast" is often all it takes to see the hidden structure — that's the whole idea behind P vs NP: some approximations are easy even when the exact answer is hard.