The LLL algorithm's main goal is to take a "bad" basis (with long, nearly parallel vectors) and turn it into a "good" basis (with short, nearly orthogonal vectors) that generates the exact same lattice.
In 2D, LLL is just a more formal version of Gauss's Reduction Algorithm. It repeatedly does two simple steps:
Reduce: Subtract the shortest vector from the longer one to make it shorter.
Swap: If the "longer" vector becomes shorter than the "shortest" one, swap them.
Mini Example: 2D LLL (Gauss's Reduction)
Let's start with a "bad" 2D basis. These vectors are long and very close to each other.
-
Initial Basis:
$\mathbf{b_1} = (1, 9)$
$\mathbf{b_2} = (1, 10)$
The algorithm works in loops.
Loop 1
-
Reduce: We want to make $\mathbf{b_2}$ shorter by subtracting a multiple of $\mathbf{b_1}$. The best multiple $q$ is the closest integer to $\frac{\mathbf{b_1} \cdot \mathbf{b_2}}{\|\mathbf{b_1}\|^2}$.
$\mathbf{b_1} \cdot \mathbf{b_2} = (1 \cdot 1) + (9 \cdot 10) = 91$
$\|\mathbf{b_1}\|^2 = 1^2 + 9^2 = 82$
$q = \text{round}(91 / 82) = \text{round}(1.11) = 1$
**New $\mathbf{b_2}$} $\leftarrow \mathbf{b_2} - 1 \cdot \mathbf{b_1} = (1, 10) - (1, 9) = \mathbf{(0, 1)}$
Current Basis: $\{\mathbf{b_1} = (1, 9), \mathbf{b_2} = (0, 1)\}$
-
Swap Check (Lovász Condition): Is $\mathbf{b_1}$ "short enough" compared to $\mathbf{b_2}$? A simple check (Gauss's version) is: Is $\|\mathbf{b_1}\| \le \|\mathbf{b_2}\|$?
$\|\mathbf{b_1}\|^2 = 82$
$\|\mathbf{b_2}\|^2 = 1$
The condition is FALSE (82 is not $\le 1$). We must swap.
Basis after Loop 1: $\{\mathbf{b_1} = (0, 1), \mathbf{b_2} = (1, 9)\}$
Loop 2
-
Reduce: Make the new $\mathbf{b_2}$ shorter by subtracting a multiple of the new $\mathbf{b_1}$.
$q = \text{round}\left( \frac{\mathbf{b_1} \cdot \mathbf{b_2}}{\|\mathbf{b_1}\|^2} \right) = \text{round}\left( \frac{(0 \cdot 1) + (1 \cdot 9)}{1^2} \right) = \text{round}(9) = 9$
**New $\mathbf{b_2}$} $\leftarrow \mathbf{b_2} - 9 \cdot \mathbf{b_1} = (1, 9) - 9 \cdot (0, 1) = (1, 9) - (0, 9) = \mathbf{(1, 0)}$
Current Basis: $\{\mathbf{b_1} = (0, 1), \mathbf{b_2} = (1, 0)\}$
-
Swap Check: Is $\|\mathbf{b_1}\|^2 \le \|\mathbf{b_2}\|^2$?
$\|\mathbf{b_1}\|^2 = 1$
$\|\mathbf{b_2}\|^2 = 1$
The condition is TRUE (1 is $\le 1$). We do not swap.
The algorithm terminates.
Original "Bad" Basis: $\{(1, 9), (1, 10)\}$
LLL-Reduced "Good" Basis: $\{(0, 1), (1, 0)\}$
We found the shortest, most orthogonal basis for the lattice, which is just the standard integer grid $Z^2$.
Use Cases for 2D and 3D
You're right that solving SVP in 2D and 3D is "easy." We don't use LLL in low dimensions to solve hard crypto problems, but as a powerful tool for other mathematical problems.
2D Use Case: Finding Good Fractions (Diophantine Approximation)
Problem: Find a good, simple fraction $p/q$ that approximates an irrational number $\alpha$, like $\pi \approx 3.14159265...$
How LLL works:
-
We build a 2D lattice basis using $\alpha$ and a large constant $C$:
$\mathbf{b_1} = (1, C \cdot \alpha)$
$\mathbf{b_2} = (0, C)$
-
Any vector in this lattice looks like:
q⋅b1−p⋅b2=(q,C⋅qα)−(0,C⋅p)=(q,C(qα−p))
We run LLL on this basis to find a very short vector. A short vector will have a small $q$ (first component) and a very small $C(q\alpha - p)$ (second component).
-
If C(qα−p) is tiny, it means qα−p≈0, which rearranges to:
α≈p/q
Running this for $\alpha = \pi$ and a large $C$ will quickly spit out the short vector corresponding to the famous approximation $\mathbf{22/7}$ and the even better one, $\mathbf{355/113}$.
3D Use Case: Finding Integer Relations (The PSLQ Algorithm)
Problem: Find if a set of numbers are related by integers. For example, do $\log(2)$, $\log(3)$, and $\log(5)$ have an integer relation? (i.e., can you find integers $a, b, c$ such that $a \cdot \log(2) + b \cdot \log(3) + c \cdot \log(5) = 0$?)
How LLL works:
This is the same idea as 2D, but in 3D. We build a lattice where a short vector would prove a relationship.
-
We build a 3D basis:
$\mathbf{b_1} = (1, 0, C \cdot \log(2))$
$\mathbf{b_2} = (0, 1, C \cdot \log(3))$
$\mathbf{b_3} = (0, 0, C \cdot \log(5))$
-
Any vector in this lattice is:
a⋅b1+b⋅b2+c⋅b3=(a,b,C(a⋅log(2)+b⋅log(3)+c⋅log(5)))
We run LLL to find the shortest vector in this lattice.
If the shortest vector found is very short, its third component must be almost zero. This means we found integers $a, b, c$ such that $a \cdot \log(2) + b \cdot \log(3) + c \cdot \log(5) \approx 0$.
(In this specific case, these numbers are known to be unrelated, so LLL would return a vector that isn't "short enough," proving no simple integer relation exists).
This technique was also the original motivation for LLL: factoring polynomials with rational coefficients.