LLL Lattice Reduction

Introduction

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.

Try It

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">The gray dots are one 2D lattice — every point reachable as a whole-number combination of the two basis vectors, drawn as red (b1) and blue (b2) arrows. The starting basis is long and nearly parallel.</p>
<div class="controls">
  <button id="step" type="button">Step</button>
  <button id="reduce" type="button">Reduce fully</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="info-bar">
  <span>Lengths: <b id="lens">—</b></span>
  <span>Angle: <b id="angle">—</b></span>
  <span>Steps: <b id="steps">0</b></span>
</div>
<canvas id="cv" width="480" height="340"></canvas>
<div class="status" id="status">Click Step to run one move of LLL, or Reduce fully to finish at once.</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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 2D lattice reduction: LLL untangles a skewed basis into a short, nearly-orthogonal one.
// The algorithm alternates two moves until neither applies:
// Size-reduce: subtract the nearest integer multiple of b1 from b2.
// Swap b1 and b2 whenever that shortens the pair (the Lovasz condition).
// Repeat until a single pass changes nothing.

const DELTA = 0.75; // the Lovasz condition parameter (3/4 is the classic choice)
// A deliberately long, nearly-parallel starting basis for the same lattice.
const INIT = [[27, 11], [35, 14]];

let b1, b2, stepCount, done;

function dot(a, b) { return a[0] * b[0] + a[1] * b[1]; }
function norm2(a) { return dot(a, a); }
function len(a) { return Math.sqrt(norm2(a)); }

function reset() {
  b1 = [...INIT[0]];
  b2 = [...INIT[1]];
  stepCount = 0;
  done = false;
  document.getElementById('step').disabled = false;
  document.getElementById('reduce').disabled = false;
  setStatus('Click Step to run one move of LLL, or Reduce fully to finish at once.', '');
  updateUI();
}

// Runs exactly one move of the algorithm; returns false once no move changes anything.
function lllStep() {
  if (done) return false;

  // If b2 has a large projection onto b1, remove the integer part of it.
  const mu = dot(b2, b1) / norm2(b1);
  const rounded = Math.round(mu);
  if (rounded !== 0) {
    b2 = [b2[0] - rounded * b1[0], b2[1] - rounded * b1[1]];
    stepCount++;
    return true;
  }

  // Otherwise check whether swapping the vectors would shorten the shorter one.
  const mu2 = dot(b2, b1) / norm2(b1);
  const b2star = [b2[0] - mu2 * b1[0], b2[1] - mu2 * b1[1]];
  if (norm2(b2star) < (DELTA - mu2 * mu2) * norm2(b1)) {
    const tmp = b1; b1 = b2; b2 = tmp; // swap keeps the same lattice, just reorders the basis
    stepCount++;
    return true;
  }

  done = true;
  return false;
}

function angleDeg() {
  const cosA = dot(b1, b2) / (len(b1) * len(b2));
  const a = Math.acos(Math.min(1, Math.max(-1, cosA))) * 180 / Math.PI;
  return a > 90 ? 180 - a : a;
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

function updateUI() {
  document.getElementById('steps').textContent = stepCount;
  document.getElementById('lens').textContent =
    len(b1).toFixed(2) + ', ' + len(b2).toFixed(2);
  document.getElementById('angle').textContent = angleDeg().toFixed(1) + '°';
  if (done) {
    document.getElementById('step').disabled = true;
    document.getElementById('reduce').disabled = true;
    setStatus(i18nFmt('Reduced after %n% step(s) — same lattice, short and nearly orthogonal basis.', { n: stepCount }), 'done');
  }
  draw();
}

// Canvas drawing helpers below - no algorithm logic here.
const CV_W = 480, CV_H = 340;
const ORIGIN = [CV_W / 2, CV_H / 2];

function draw() {
  const cv = document.getElementById('cv');
  const ctx = cv.getContext('2d');
  ctx.clearRect(0, 0, CV_W, CV_H);

  // Pick a zoom level so the arrows and nearby lattice points fit on the canvas.
  const maxCoord = Math.max(
    Math.abs(INIT[0][0]), Math.abs(INIT[0][1]),
    Math.abs(INIT[1][0]), Math.abs(INIT[1][1]), 1
  ) * 2.6;
  const scale = Math.min(CV_W, CV_H) / 2 / maxCoord;

  function toPx(p) {
    return [ORIGIN[0] + p[0] * scale, ORIGIN[1] - p[1] * scale];
  }

  // Draw every lattice point reachable with small integer combinations of b1, b2.
  ctx.fillStyle = '#c3ccd6';
  const range = 6;
  for (let i = -range; i <= range; i++) {
    for (let j = -range; j <= range; j++) {
      const x = i * b1[0] + j * b2[0];
      const y = i * b1[1] + j * b2[1];
      const [px, py] = toPx([x, y]);
      if (px < -10 || px > CV_W + 10 || py < -10 || py > CV_H + 10) continue;
      ctx.beginPath();
      ctx.arc(px, py, 2.2, 0, Math.PI * 2);
      ctx.fill();
    }
  }

  // Faint reference axes through the origin.
  ctx.strokeStyle = '#e2e8ef';
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(0, ORIGIN[1]); ctx.lineTo(CV_W, ORIGIN[1]);
  ctx.moveTo(ORIGIN[0], 0); ctx.lineTo(ORIGIN[0], CV_H);
  ctx.stroke();

  // Draw the two current basis vectors as arrows from the origin.
  drawArrow(ctx, ORIGIN, toPx(b1), '#e63946', 'b1');
  drawArrow(ctx, ORIGIN, toPx(b2), '#457b9d', 'b2');
}

function drawArrow(ctx, from, to, color, label) {
  ctx.strokeStyle = color;
  ctx.fillStyle = color;
  ctx.lineWidth = 2.4;
  ctx.beginPath();
  ctx.moveTo(from[0], from[1]);
  ctx.lineTo(to[0], to[1]);
  ctx.stroke();

  const dx = to[0] - from[0], dy = to[1] - from[1];
  const ang = Math.atan2(dy, dx);
  const headLen = 10;
  ctx.beginPath();
  ctx.moveTo(to[0], to[1]);
  ctx.lineTo(to[0] - headLen * Math.cos(ang - Math.PI / 7), to[1] - headLen * Math.sin(ang - Math.PI / 7));
  ctx.lineTo(to[0] - headLen * Math.cos(ang + Math.PI / 7), to[1] - headLen * Math.sin(ang + Math.PI / 7));
  ctx.closePath();
  ctx.fill();

  ctx.font = '700 13px ui-monospace, monospace';
  ctx.fillText(label, to[0] + 6, to[1] - 6);
}

document.getElementById('step').addEventListener('click', () => {
  lllStep();
  updateUI();
});
document.getElementById('reduce').addEventListener('click', () => {
  let guard = 0;
  while (lllStep() && guard < 2000) guard++;
  updateUI();
});
document.getElementById('reset').addEventListener('click', reset);

reset();

<p class="hint">The gray dots are one 2D lattice — every point reachable as a whole-number combination of the two basis vectors, drawn as red (b1) and blue (b2) arrows. The starting basis is long and nearly parallel.</p>
<div class="controls">
  <button id="step" type="button">Step</button>
  <button id="reduce" type="button">Reduce fully</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="info-bar">
  <span>Lengths: <b id="lens">—</b></span>
  <span>Angle: <b id="angle">—</b></span>
  <span>Steps: <b id="steps">0</b></span>
</div>
<canvas id="cv" width="480" height="340"></canvas>
<div class="status" id="status">Click Step to run one move of LLL, or Reduce fully to finish at once.</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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 2D lattice reduction: LLL untangles a skewed basis into a short, nearly-orthogonal one.
// The algorithm alternates two moves until neither applies:
// Size-reduce: subtract the nearest integer multiple of b1 from b2.
// Swap b1 and b2 whenever that shortens the pair (the Lovasz condition).
// Repeat until a single pass changes nothing.

const DELTA = 0.75; // the Lovasz condition parameter (3/4 is the classic choice)
// A deliberately long, nearly-parallel starting basis for the same lattice.
const INIT = [[27, 11], [35, 14]];

let b1, b2, stepCount, done;

function dot(a, b) { return a[0] * b[0] + a[1] * b[1]; }
function norm2(a) { return dot(a, a); }
function len(a) { return Math.sqrt(norm2(a)); }

function reset() {
  b1 = [...INIT[0]];
  b2 = [...INIT[1]];
  stepCount = 0;
  done = false;
  document.getElementById('step').disabled = false;
  document.getElementById('reduce').disabled = false;
  setStatus('Click Step to run one move of LLL, or Reduce fully to finish at once.', '');
  updateUI();
}

// Runs exactly one move of the algorithm; returns false once no move changes anything.
function lllStep() {
  if (done) return false;

  // If b2 has a large projection onto b1, remove the integer part of it.
  const mu = dot(b2, b1) / norm2(b1);
  const rounded = Math.round(mu);
  if (rounded !== 0) {
    b2 = [b2[0] - rounded * b1[0], b2[1] - rounded * b1[1]];
    stepCount++;
    return true;
  }

  // Otherwise check whether swapping the vectors would shorten the shorter one.
  const mu2 = dot(b2, b1) / norm2(b1);
  const b2star = [b2[0] - mu2 * b1[0], b2[1] - mu2 * b1[1]];
  if (norm2(b2star) < (DELTA - mu2 * mu2) * norm2(b1)) {
    const tmp = b1; b1 = b2; b2 = tmp; // swap keeps the same lattice, just reorders the basis
    stepCount++;
    return true;
  }

  done = true;
  return false;
}

function angleDeg() {
  const cosA = dot(b1, b2) / (len(b1) * len(b2));
  const a = Math.acos(Math.min(1, Math.max(-1, cosA))) * 180 / Math.PI;
  return a > 90 ? 180 - a : a;
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

function updateUI() {
  document.getElementById('steps').textContent = stepCount;
  document.getElementById('lens').textContent =
    len(b1).toFixed(2) + ', ' + len(b2).toFixed(2);
  document.getElementById('angle').textContent = angleDeg().toFixed(1) + '°';
  if (done) {
    document.getElementById('step').disabled = true;
    document.getElementById('reduce').disabled = true;
    setStatus(i18nFmt('Reduced after %n% step(s) — same lattice, short and nearly orthogonal basis.', { n: stepCount }), 'done');
  }
  draw();
}

// Canvas drawing helpers below - no algorithm logic here.
const CV_W = 480, CV_H = 340;
const ORIGIN = [CV_W / 2, CV_H / 2];

function draw() {
  const cv = document.getElementById('cv');
  const ctx = cv.getContext('2d');
  ctx.clearRect(0, 0, CV_W, CV_H);

  // Pick a zoom level so the arrows and nearby lattice points fit on the canvas.
  const maxCoord = Math.max(
    Math.abs(INIT[0][0]), Math.abs(INIT[0][1]),
    Math.abs(INIT[1][0]), Math.abs(INIT[1][1]), 1
  ) * 2.6;
  const scale = Math.min(CV_W, CV_H) / 2 / maxCoord;

  function toPx(p) {
    return [ORIGIN[0] + p[0] * scale, ORIGIN[1] - p[1] * scale];
  }

  // Draw every lattice point reachable with small integer combinations of b1, b2.
  ctx.fillStyle = '#c3ccd6';
  const range = 6;
  for (let i = -range; i <= range; i++) {
    for (let j = -range; j <= range; j++) {
      const x = i * b1[0] + j * b2[0];
      const y = i * b1[1] + j * b2[1];
      const [px, py] = toPx([x, y]);
      if (px < -10 || px > CV_W + 10 || py < -10 || py > CV_H + 10) continue;
      ctx.beginPath();
      ctx.arc(px, py, 2.2, 0, Math.PI * 2);
      ctx.fill();
    }
  }

  // Faint reference axes through the origin.
  ctx.strokeStyle = '#e2e8ef';
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(0, ORIGIN[1]); ctx.lineTo(CV_W, ORIGIN[1]);
  ctx.moveTo(ORIGIN[0], 0); ctx.lineTo(ORIGIN[0], CV_H);
  ctx.stroke();

  // Draw the two current basis vectors as arrows from the origin.
  drawArrow(ctx, ORIGIN, toPx(b1), '#e63946', 'b1');
  drawArrow(ctx, ORIGIN, toPx(b2), '#457b9d', 'b2');
}

function drawArrow(ctx, from, to, color, label) {
  ctx.strokeStyle = color;
  ctx.fillStyle = color;
  ctx.lineWidth = 2.4;
  ctx.beginPath();
  ctx.moveTo(from[0], from[1]);
  ctx.lineTo(to[0], to[1]);
  ctx.stroke();

  const dx = to[0] - from[0], dy = to[1] - from[1];
  const ang = Math.atan2(dy, dx);
  const headLen = 10;
  ctx.beginPath();
  ctx.moveTo(to[0], to[1]);
  ctx.lineTo(to[0] - headLen * Math.cos(ang - Math.PI / 7), to[1] - headLen * Math.sin(ang - Math.PI / 7));
  ctx.lineTo(to[0] - headLen * Math.cos(ang + Math.PI / 7), to[1] - headLen * Math.sin(ang + Math.PI / 7));
  ctx.closePath();
  ctx.fill();

  ctx.font = '700 13px ui-monospace, monospace';
  ctx.fillText(label, to[0] + 6, to[1] - 6);
}

document.getElementById('step').addEventListener('click', () => {
  lllStep();
  updateUI();
});
document.getElementById('reduce').addEventListener('click', () => {
  let guard = 0;
  while (lllStep() && guard < 2000) guard++;
  updateUI();
});
document.getElementById('reset').addEventListener('click', reset);

reset();

Result

Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lll-lattice-reduction/Content licensed under CC BY-NC 4.0.

Cookies & privacy

How to make a tangled grid of points look tidy again