08c-lll-algorithm.ipynb

Kernel: SageMath 10.5

The LLL Algorithm

Module 08c | Lattices and Post-Quantum

The most important algorithm in lattice theory finds short vectors in polynomial time, but not short enough to break modern cryptography.

Motivating Question: Given a terrible basis with long, nearly-parallel vectors, can we algorithmically find a "nice" basis with short, nearly-orthogonal vectors? And can we do it in polynomial time?

In notebook 08b we saw that finding the shortest vector in a lattice (SVP) is hard, believed to require exponential time in general. But what if we settle for an approximately short vector? In 1982, Arjen Lenstra, Hendrik Lenstra, and László Lovász discovered that a clever combination of Gram-Schmidt orthogonalization and a simple swap-and-reduce loop can transform any lattice basis into a "reduced" one with provably short vectors, all in polynomial time. Their algorithm, LLL, remains the single most important tool in computational lattice theory.

Objectives

By the end of this notebook you will be able to:

1. Compute the Gram-Schmidt orthogonalization (GSO) of a lattice basis by hand and in SageMath

2. State and check the two LLL conditions (size-reduction and the Lovász condition)

3. Trace the LLL algorithm step-by-step on a small example

4. Measure basis quality using orthogonality defect and Hermite factor

5. Explain why LLL is powerful enough to break early lattice schemes but not modern ones like Kyber

Prerequisites

• Completion of The Shortest Vector Problem

• Familiarity with lattices, bases, and the concept of SVP

• Basic linear algebra: dot products, vector norms, projections

Bridge from 08b: We ended notebook 08b knowing that SVP is hard in the worst case. But "hard in the worst case" doesn't mean "impossible to approximate." LLL gives us an efficient algorithm that approximately solves SVP, and that approximation is good enough to break many cryptographic schemes, though not all.

1. Gram-Schmidt Orthogonalization: The Geometric Backbone

Before we can understand LLL, we need the Gram-Schmidt orthogonalization (GSO). Given a basis $\{\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_n\}$, GSO produces an orthogonal basis $\{\mathbf{b}_1^*, \mathbf{b}_2^*, \ldots, \mathbf{b}_n^*\}$ for the same vector space (but not the same lattice!) using the formulas:

$$\mathbf{b}_i^* = \mathbf{b}_i - \sum_{j=1}^{i-1} \mu_{i,j} \, \mathbf{b}_j^*, \qquad \text{where } \mu_{i,j} = \frac{\langle \mathbf{b}_i, \mathbf{b}_j^* \rangle}{\langle \mathbf{b}_j^*, \mathbf{b}_j^* \rangle}$$

The coefficients $\mu_{i,j}$ measure how much of $\mathbf{b}_j^*$ we need to subtract from $\mathbf{b}_i$ to make it orthogonal to all previous vectors.

Key insight: The GSO vectors $\mathbf{b}_i^*$ are the "orthogonal components" of the basis. Their norms $\|\mathbf{b}_i^*\|$ tell us how much "new" length each basis vector contributes in a direction orthogonal to all previous vectors.

Let's start with the simplest case: two vectors in $\mathbb{R}^2$.

# Gram-Schmidt in 2D, by hand, then verified with SageMath
b1 = vector(QQ, [3, 1])
b2 = vector(QQ, [2, 3])

# Step 1: b1* = b1 (first vector is unchanged)
b1_star = b1

# Step 2: compute mu_{2,1} and subtract the projection
mu_21 = b2.dot_product(b1_star) / b1_star.dot_product(b1_star)
b2_star = b2 - mu_21 * b1_star

print(f'b1       = {b1}')
print(f'b2       = {b2}')
print(f'mu_21    = {mu_21} = {float(mu_21):.4f}')
print(f'b1*      = {b1_star}')
print(f'b2*      = {b2_star}')
print(f'\nVerification: b1* . b2* = {b1_star.dot_product(b2_star)}  (should be 0)')

# SageMath has a built-in Gram-Schmidt method
B = matrix(QQ, [b1, b2])
G, mu_matrix = B.gram_schmidt()
print(f'\nSageMath GSO basis:\n{G}')
print(f'Mu coefficients:\n{mu_matrix}')
print(f'Our manual b2* matches SageMath: {b2_star == G[1]}')

GSO in 3D

Now let's see the pattern with three vectors. Each new vector gets projected onto all previous GSO vectors.

# GSO for a 3D basis
B3 = matrix(QQ, [[1, 1, 1],
                  [-1, 0, 2],
                  [3, 5, 6]])

G3, mu3 = B3.gram_schmidt()

print('Original basis:')
for i in range(3):
    print(f'  b{i+1}  = {B3[i]}  (norm = {float(B3[i].norm()):.4f})')

print('\nGSO basis:')
for i in range(3):
    print(f'  b{i+1}* = {G3[i]}  (norm = {float(G3[i].norm()):.4f})')

print(f'\nMu matrix:\n{mu3}')

# Verify orthogonality
print(f'\nb1*.b2* = {G3[0].dot_product(G3[1])}  (should be 0)')
print(f'b1*.b3* = {G3[0].dot_product(G3[2])}  (should be 0)')
print(f'b2*.b3* = {G3[1].dot_product(G3[2])}  (should be 0)')

Important: The GSO vectors $\mathbf{b}_i^*$ are not lattice vectors in general (they have rational coordinates). GSO tells us about the geometry of the basis, but we cannot simply use the GSO basis as our lattice basis. LLL works with the original integer basis while using the GSO vectors as a guide.

2. The LLL Conditions

A basis $\{\mathbf{b}_1, \ldots, \mathbf{b}_n\}$ is LLL-reduced (with parameter $\delta$, typically $\delta = 3/4$) if two conditions hold:

Condition 1: Size-Reduced

$$|\mu_{i,j}| \le \frac{1}{2} \quad \text{for all } 1 \le j < i \le n$$

This means each basis vector has been "cleaned up" — its projections onto earlier GSO vectors are at most half. If $|\mu_{i,j}| > 1/2$, we can size-reduce by replacing $\mathbf{b}_i \leftarrow \mathbf{b}_i - \lceil \mu_{i,j} \rfloor \, \mathbf{b}_j$ (where $\lceil \cdot \rfloor$ is rounding to the nearest integer).

Condition 2: Lovász Condition

$$\|\mathbf{b}_i^*\|^2 \ge \left(\delta - \mu_{i,i-1}^2\right) \|\mathbf{b}_{i-1}^*\|^2 \quad \text{for all } 2 \le i \le n$$

This prevents the GSO norms from decreasing too quickly. If the condition fails for index $i$, we swap $\mathbf{b}_i$ and $\mathbf{b}_{i-1}$.

The standard choice $\delta = 3/4$ gives a good balance between reduction quality and speed. Increasing $\delta$ toward 1 gives better reduction but slower convergence.

def check_lll_conditions(B, delta=3/4):
    """
    Check whether basis B satisfies the LLL conditions.
    Returns a detailed report.
    """
    B = matrix(QQ, B)
    n = B.nrows()
    G, mu = B.gram_schmidt()
    
    print('=== LLL Condition Check ===')
    print(f'Basis ({n} vectors), delta = {delta}\n')
    
    # Check size-reduction
    size_reduced = True
    print('Condition 1 (Size-Reduced): |mu_{i,j}| <= 1/2')
    for i in range(1, n):
        for j in range(i):
            mu_val = mu[i][j]
            ok = abs(mu_val) <= 1/2
            status = 'OK' if ok else 'FAIL'
            print(f'  mu_{{{i+1},{j+1}}} = {float(mu_val):+.4f}  [{status}]')
            if not ok:
                size_reduced = False
    
    # Check Lovasz condition
    lovasz_ok = True
    print(f'\nCondition 2 (Lovasz): ||b*_i||^2 >= (delta - mu^2_{{i,i-1}}) * ||b*_{{i-1}}||^2')
    for i in range(1, n):
        norm_i_sq = G[i].dot_product(G[i])
        norm_im1_sq = G[i-1].dot_product(G[i-1])
        mu_val = mu[i][i-1]
        threshold = (delta - mu_val^2) * norm_im1_sq
        ok = norm_i_sq >= threshold
        status = 'OK' if ok else 'FAIL'
        print(f'  i={i+1}: ||b*_{i+1}||^2 = {float(norm_i_sq):.4f} '
              f'>= ({delta} - {float(mu_val^2):.4f}) * {float(norm_im1_sq):.4f} '
              f'= {float(threshold):.4f}  [{status}]')
        if not ok:
            lovasz_ok = False
    
    print(f'\nLLL-reduced? {size_reduced and lovasz_ok}')
    return size_reduced and lovasz_ok

# Test on a non-reduced basis
B_bad = matrix(ZZ, [[201, 37], [1648, 297]])
print('--- Bad basis ---')
check_lll_conditions(B_bad)

Checkpoint: Look at the output above. Which condition failed — size-reduction, Lovász, or both? What does the failure of each condition tell you geometrically about the basis?

3. Step-by-Step LLL on a 2D Example

Let's trace every single step of the LLL algorithm on a small example. This is the best way to build intuition.

Input basis: $$\mathbf{b}_1 = (201, 37), \quad \mathbf{b}_2 = (1648, 297)$$

This is a "bad" basis: the vectors are long and nearly parallel.

def lll_step_by_step(B, delta=QQ(3)/QQ(4)):
    """
    LLL algorithm with verbose output showing every step.
    Works over QQ for exact arithmetic.
    """
    B = matrix(QQ, B)
    n = B.nrows()
    step = 0
    
    print(f'=== LLL Algorithm (delta={delta}) ===')
    print(f'Input basis:')
    for i in range(n):
        print(f'  b{i+1} = {B[i]}  (norm = {float(B[i].norm()):.2f})')
    print()
    
    k = 1
    while k < n:
        step += 1
        G, mu = B.gram_schmidt()
        
        print(f'--- Step {step}: processing index k={k+1} ---')
        
        # Size-reduce b_k against all previous vectors
        for j in range(k-1, -1, -1):
            mu_val = mu[k][j]
            if abs(mu_val) > QQ(1)/QQ(2):
                r = mu_val.round()
                print(f'  Size-reduce: mu_{{{k+1},{j+1}}} = {float(mu_val):.4f}, '
                      f'round = {r}')
                print(f'    b{k+1} <- b{k+1} - {r}*b{j+1} = {B[k]} - {r}*{B[j]}')
                B[k] = B[k] - r * B[j]
                print(f'    b{k+1} = {B[k]}  (norm = {float(B[k].norm()):.2f})')
                G, mu = B.gram_schmidt()
        
        # Check Lovasz condition
        norm_k_sq = G[k].dot_product(G[k])
        norm_km1_sq = G[k-1].dot_product(G[k-1])
        mu_val = mu[k][k-1]
        lovasz_threshold = (delta - mu_val^2) * norm_km1_sq
        
        print(f'  Lovasz check: ||b*_{k+1}||^2 = {float(norm_k_sq):.4f} '
              f'>= {float(lovasz_threshold):.4f}?')
        
        if norm_k_sq >= lovasz_threshold:
            print(f'  Lovasz PASSES -> move to k={k+2}')
            k += 1
        else:
            print(f'  Lovasz FAILS -> SWAP b{k} and b{k+1}, back to k={k}')
            B.swap_rows(k-1, k)
            k = max(k-1, 1)
        
        print(f'  Current basis:')
        for i in range(n):
            print(f'    b{i+1} = {B[i]}  (norm = {float(B[i].norm()):.2f})')
        print()
    
    print(f'=== Done in {step} steps ===')
    print(f'Output basis:')
    for i in range(n):
        print(f'  b{i+1} = {B[i]}  (norm = {float(B[i].norm()):.2f})')
    return matrix(ZZ, B)

# Run on our bad basis
B_bad = matrix(ZZ, [[201, 37], [1648, 297]])
B_reduced = lll_step_by_step(B_bad)

# Verify the result is LLL-reduced and matches SageMath
print('=== Verification ===')
print(f'Output basis:\n{B_reduced}\n')
check_lll_conditions(B_reduced)

B_sage = matrix(ZZ, [[201, 37], [1648, 297]]).LLL()
print(f'\nSageMath LLL gives:\n{B_sage}')
print(f'Same result (up to signs)? {B_reduced == B_sage or B_reduced == -B_sage}')

Checkpoint: In the step-by-step trace above, find the swap step. Before the swap, which vector was longer — $\mathbf{b}_1$ or $\mathbf{b}_2$? After the swap and re-reduction, are the vectors more nearly orthogonal? (Hint: compute the angle between them.)

4. SageMath's Built-in LLL

In practice, you will use M.LLL() on an integer matrix. Let's see the dramatic improvement it produces on larger, more badly-conditioned bases.

# A badly-conditioned 3D basis
B = matrix(ZZ, [[15, 23, 11],
                 [46, 79, 31],
                 [32, 48, 97]])

L = B.LLL()

print('BEFORE LLL:')
for i in range(3):
    print(f'  b{i+1} = {list(B[i]):>20s}  norm = {float(B[i].norm()):8.2f}')

print('\nAFTER LLL:')
for i in range(3):
    print(f'  b{i+1} = {list(L[i]):>20s}  norm = {float(L[i].norm()):8.2f}')

# Check that both bases span the same lattice (transition matrix has det +/- 1)
T = B.solve_left(L)
print(f'\nTransition matrix determinant: {T.det()} (must be +/- 1)')

# A larger example: random 6D lattice worsened by a unimodular transform
set_random_seed(42)
n = 6
B_random = random_matrix(ZZ, n, n, x=-100, y=100)

# Upper-triangular unimodular matrix (det = 1) to scramble the basis
U_bad = matrix(ZZ, [[1,3,2,0,-1,4],
                     [0,1,0,2,1,-3],
                     [0,0,1,1,0,2],
                     [0,0,0,1,0,1],
                     [0,0,0,0,1,0],
                     [0,0,0,0,0,1]])
B_bad = U_bad * B_random
L_good = B_bad.LLL()

print(f'Dimension: {n}')
print(f'\nBefore LLL, vector norms:')
for i in range(n):
    print(f'  ||b{i+1}|| = {float(B_bad[i].norm()):.2f}')

print(f'\nAfter LLL, vector norms:')
for i in range(n):
    print(f'  ||b{i+1}|| = {float(L_good[i].norm()):.2f}')

print(f'\nShortest vector norm before: {float(min(B_bad[i].norm() for i in range(n))):.2f}')
print(f'Shortest vector norm after:  {float(L_good[0].norm()):.2f}')

5. Quality Metrics: How Good Is Our Reduced Basis?

We need quantitative ways to measure how "nice" a basis is. Two key metrics:

Orthogonality Defect

$$\text{od}(B) = \frac{\prod_{i=1}^n \|\mathbf{b}_i\|}{|\det(B)|}$$

By Hadamard's inequality, $\text{od}(B) \ge 1$, with equality only when the basis is perfectly orthogonal. The closer to 1, the better.

Hermite Factor

$$\gamma = \frac{\|\mathbf{b}_1\|}{\det(L)^{1/n}}$$

This measures how short the first (shortest) vector is relative to the lattice determinant. LLL guarantees $\gamma \le 2^{(n-1)/4}$. Smaller is better.

def basis_quality(B, label=''):
    """
    Compute and display quality metrics for a lattice basis.
    """
    B = matrix(QQ, B)
    n = B.nrows()
    
    # Orthogonality defect
    norms_product = prod(B[i].norm() for i in range(n))
    det_abs = abs(B.det())
    orth_defect = float(norms_product / det_abs)
    
    # Hermite factor
    b1_norm = float(B[0].norm())
    det_root = float(det_abs^(1/n))
    hermite = b1_norm / det_root
    
    if label:
        print(f'--- {label} ---')
    print(f'  ||b_1||              = {b1_norm:.4f}')
    print(f'  |det(B)|             = {float(det_abs):.4f}')
    print(f'  Orthogonality defect = {orth_defect:.4f}  (1.0 = perfect)')
    print(f'  Hermite factor       = {hermite:.4f}')
    return orth_defect, hermite

# Compare before and after LLL
B = matrix(ZZ, [[201, 37], [1648, 297]])
L = B.LLL()

basis_quality(B, 'Before LLL')
print()
basis_quality(L, 'After LLL')

Common mistake: "LLL finds the shortest vector." No! LLL finds an approximately shortest vector. The first vector $\mathbf{b}_1$ of the LLL-reduced basis satisfies:

$$\|\mathbf{b}_1\| \le 2^{(n-1)/2} \cdot \lambda_1(L)$$

where $\lambda_1(L)$ is the true shortest vector length. This approximation factor $2^{(n-1)/2}$ grows exponentially with dimension. In 2D it's harmless ($\sqrt{2} \approx 1.41$), but in 500D it's astronomically large ($2^{249.5}$). LLL does not solve SVP — it solves an exponential approximation of SVP, and it does so in polynomial time.

6. LLL Guarantees and Approximation Factor

Let's make the guarantees concrete. The LLL algorithm (with $\delta = 3/4$) guarantees:

1. Running time: Polynomial in $n$ and the bit-length of the input — specifically $O(n^5 d \log^3 B)$ where $d$ is the dimension and $B$ bounds the entries.

2. Output quality: The first vector satisfies $\|\mathbf{b}_1\| \le 2^{(n-1)/2} \cdot \lambda_1(L)$.

3. All vectors bounded: For each $i$, $\|\mathbf{b}_i\| \le 2^{(n-1)/2} \cdot \lambda_i(L)$ where $\lambda_i$ is the $i$-th successive minimum.

Let's visualize how the approximation factor grows with dimension:

# Approximation factor 2^((n-1)/2) as a function of dimension
print('LLL approximation factor 2^((n-1)/2):')
print(f'{"Dim":>5s}  {"Factor":>15s}  {"log10(Factor)":>15s}')
for n in [2, 5, 10, 20, 50, 100, 200, 500]:
    factor = 2^((n-1)/2)
    log_f = float((n-1)/2 * log(2.0, 10))
    if n <= 50:
        print(f'{n:5d}  {float(factor):15.1f}  {log_f:15.2f}')
    else:
        print(f'{n:5d}  {"2^" + str((n-1)/2):>15s}  {log_f:15.2f}')

# Plot the log of the approximation factor
p = list_plot([(n, float((n-1)/2)) for n in range(2, 101)],
              plotjoined=True, axes_labels=['Dimension $n$', '$\\log_2$ approx factor'],
              title='LLL Approximation Factor Growth', color='red', thickness=2)
show(p, figsize=(8, 4))

The approximation factor grows linearly on a log scale, meaning it's exponential in the dimension. This is the fundamental limitation of LLL:

• In low dimensions (say $n \le 40$), LLL often finds vectors much shorter than the worst-case guarantee — sometimes close to the actual shortest vector.

• In high dimensions (say $n \ge 200$), the approximation factor becomes so large that LLL-reduced vectors can be far from optimal.

This gap is precisely what modern lattice-based cryptography exploits.

7. Applications: Breaking Things with LLL

LLL is an incredibly versatile tool. Here we demonstrate two classic applications.

Application 1: Breaking Low-Dimensional Knapsack Cryptography

The subset-sum (knapsack) problem was once proposed as a basis for public-key encryption (Merkle-Hellman, 1978). The idea: public key is a set of weights $\{a_1, \ldots, a_n\}$ and a target sum $s = \sum_{i \in S} a_i$. Finding the subset $S$ is the hard problem.

LLL can break this by embedding it as a lattice problem!

# Breaking a toy knapsack instance with LLL
set_random_seed(123)
n = 8  # dimension (number of weights)
a = [randint(1, 2^20) for _ in range(n)]  # public weights

# Secret binary message
x_secret = vector(ZZ, [1, 0, 1, 1, 0, 0, 1, 0])
s = sum(a[i] * x_secret[i] for i in range(n))  # target sum

print(f'Public weights: {a}')
print(f'Target sum:     {s}')
print(f'Secret message: {x_secret}')

# Build the lattice for knapsack:
#   [ I_n  |  0 ]
#   [ a^T  | -s ]
M = matrix(ZZ, n+1, n+1)
for i in range(n):
    M[i, i] = 1          # identity block
    M[n, i] = a[i]       # weights in last row
M[n, n] = -s              # target sum (negated)

print(f'\nLattice matrix ({n+1}x{n+1}):')
print(M)

# Apply LLL
L = M.LLL()
print(f'\nLLL-reduced basis:')
print(L)

# Look for a row with entries in {0,1} and last entry 0
print(f'\nSearching for solution...')
for sign in [1, -1]:
    for i in range(n+1):
        row = sign * L[i]
        candidate = row[:n]
        if row[n] == 0 and all(c in [0, 1] for c in candidate):
            print(f'  Found in row {i}{" (negated)" if sign == -1 else ""}: {candidate}')
            print(f'  Matches secret?  {candidate == x_secret}')
            break
    else:
        continue
    break

LLL found the secret binary message by reducing the lattice! The key idea: the solution vector $(x_1, \ldots, x_n, 0)$ is a short vector in the constructed lattice (its entries are just 0s and 1s), so LLL can find it.

This is essentially how Shamir broke the Merkle-Hellman knapsack cryptosystem in 1982 — the same year LLL was published.

Application 2: Finding Integer Relations

Given real numbers $\alpha_1, \ldots, \alpha_n$, an integer relation is a vector $(m_1, \ldots, m_n) \in \mathbb{Z}^n \setminus \{0\}$ such that $\sum m_i \alpha_i = 0$. LLL can find these! Classic application: recover minimal polynomials of algebraic numbers.

# Finding the minimal polynomial of alpha = 2^(1/3) via LLL
# We know alpha^3 - 2 = 0, so the relation (coeff vector) should be (-2, 0, 0, 1)

alpha = RR(2^(1/3))
precision = 10^12  # scaling factor for real -> integer
n = 4  # we look for a degree-3 relation: c0 + c1*x + c2*x^2 + c3*x^3 = 0

# Construct the HJLS-type lattice
M_ext = matrix(ZZ, n, n+1)
for i in range(n):
    M_ext[i, i] = 1
    M_ext[i, n] = round(precision * alpha^i)

L = M_ext.LLL()

print(f'Looking for minimal polynomial of 2^(1/3)...')
print(f'\nLLL-reduced basis (first n columns = coefficients):')
for i in range(n):
    coeffs = L[i][:n]
    residual = L[i][n]
    print(f'  Row {i}: coeffs = {coeffs}, residual = {residual}')

# The row with smallest residual gives our relation
best_row = min(range(n), key=lambda i: abs(L[i][n]))
coeffs = L[best_row][:n]
print(f'\nBest relation: {coeffs[0]} + {coeffs[1]}*x + {coeffs[2]}*x^2 + {coeffs[3]}*x^3 = 0')
R.<x> = QQ[]
p = sum(coeffs[i] * x^i for i in range(n))
print(f'As polynomial: {p}')
print(f'Factors: {p.factor()}')

Crypto Foreshadowing: LLL breaks many early lattice-based schemes (knapsack crypto, certain NTRU parameters, low-exponent RSA attacks) but NOT modern ones like Kyber/ML-KEM. Why? Modern schemes are designed in dimensions $n \ge 256$ with carefully chosen parameters so that the best known lattice algorithms (even ones better than LLL, like BKZ) cannot find short enough vectors in reasonable time. In notebook 08f, we'll see exactly how Kyber's parameter selection defeats lattice reduction.

8. Limitations of LLL

Let's see empirically how LLL's quality degrades with dimension.

# Measure LLL's Hermite factor across dimensions
set_random_seed(0)

dimensions = [5, 10, 20, 30, 40, 50, 60, 70, 80]
hermite_factors = []

print(f'{"Dim":>5s}  {"||b1|| before":>15s}  {"||b1|| after":>15s}  '
      f'{"Hermite factor":>15s}  {"2^((n-1)/4)":>12s}')

for n in dimensions:
    B = random_matrix(ZZ, n, n, x=-99, y=100)
    while B.det() == 0:
        B = random_matrix(ZZ, n, n, x=-99, y=100)
    
    b1_before = float(B[0].norm())
    L = B.LLL()
    b1_after = float(L[0].norm())
    det_val = abs(B.det())
    det_root = float(det_val^(QQ(1)/QQ(n)))
    hermite = b1_after / det_root
    hermite_factors.append((n, hermite))
    theoretical_bound = float(2^((n-1)/4))
    
    print(f'{n:5d}  {b1_before:15.2f}  {b1_after:15.2f}  '
          f'{hermite:15.4f}  {theoretical_bound:12.2f}')

# Plot
p1 = list_plot(hermite_factors, plotjoined=True, color='blue',
               legend_label='Actual Hermite factor', thickness=2)
p2 = list_plot([(n, float(2^((n-1)/4))) for n in range(5, 81)],
               plotjoined=True, color='red', linestyle='dashed',
               legend_label='Theoretical bound $2^{(n-1)/4}$', thickness=2)
show(p1 + p2, axes_labels=['Dimension $n$', 'Hermite factor'],
     title='LLL Quality vs Dimension', figsize=(8, 5))

Notice that:

1. The actual Hermite factor is well below the theoretical bound (LLL performs better in practice than worst-case theory suggests).

2. Nevertheless, the Hermite factor grows with dimension — LLL produces increasingly "loose" approximations as $n$ increases.

3. For cryptographic applications like Kyber ($n \ge 256$), even running LLL (or its more powerful variant BKZ) cannot find vectors short enough to break the scheme.

This is the core insight of modern lattice-based cryptography: lattice reduction algorithms exist and are powerful, but their approximation quality degrades fast enough that we can design secure schemes by choosing dimensions and parameters carefully.

Exercises

Exercise 1 (Worked)

Problem: Apply LLL to the basis $B = \begin{pmatrix} 1 & 1 \\ 0 & 17 \end{pmatrix}$. Trace each step by hand, then verify with SageMath. Compute the Hermite factor before and after.

# Exercise 1. Worked Solution

B = matrix(ZZ, [[1, 1], [0, 17]])
print('Input basis:')
print(B)
print(f'  ||b1|| = {float(B[0].norm()):.4f}')
print(f'  ||b2|| = {float(B[1].norm()):.4f}')

# Step 1: Compute GSO
G, mu = B.gram_schmidt()
print(f'\nGSO:')
print(f'  b1* = {G[0]}, ||b1*|| = {float(G[0].norm()):.4f}')
print(f'  b2* = {G[1]}, ||b2*|| = {float(G[1].norm()):.4f}')
print(f'  mu_21 = {mu[1][0]} = {float(mu[1][0]):.4f}')

# Step 2: Size-reduce check
print(f'\n|mu_21| = {abs(mu[1][0])} <= 1/2? {abs(mu[1][0]) <= QQ(1)/QQ(2)}')

# Step 3: Check Lovasz condition
delta = QQ(3)/QQ(4)
norm_b2_star_sq = G[1].dot_product(G[1])
norm_b1_star_sq = G[0].dot_product(G[0])
threshold = (delta - mu[1][0]^2) * norm_b1_star_sq
print(f'\nLovasz: ||b2*||^2 = {norm_b2_star_sq} = {float(norm_b2_star_sq):.4f}')
print(f'  (delta - mu^2) * ||b1*||^2 = ({delta} - {mu[1][0]^2}) * {norm_b1_star_sq}')
print(f'  = {threshold} = {float(threshold):.4f}')
print(f'  Lovasz holds? {norm_b2_star_sq >= threshold}')

# Trace full algorithm and verify
print('\n--- Full LLL trace ---')
B_reduced = lll_step_by_step(B)

print('\n--- Verification ---')
L = B.LLL()
print(f'SageMath LLL:\n{L}')

print('\n--- Quality comparison ---')
basis_quality(B, 'Before LLL')
print()
basis_quality(L, 'After LLL')

Exercise 2 (Guided)

Problem: Generate a random $4 \times 4$ integer matrix with entries in $[-50, 50]$. Apply LLL. Then:

1. Compute the orthogonality defect before and after reduction.

2. Verify that all GSO coefficients $|\mu_{i,j}| \le 1/2$ in the reduced basis.

3. Verify the Lovász condition holds for all consecutive pairs.

Hints:

• Use random_matrix(ZZ, 4, 4, x=-50, y=51) to generate the matrix.

• Use the check_lll_conditions() function defined earlier.

• Use the basis_quality() function for orthogonality defect.

# Exercise 2. Fill in the blanks
set_random_seed(7)  # for reproducibility

# Step 1: Generate a random 4x4 matrix
B = random_matrix(ZZ, 4, 4, x=-50, y=51)
print('Random basis:')
print(B)

# Step 2: Apply LLL
# L = ???

# Step 3: Compute orthogonality defect before and after
# Hint: basis_quality(B, 'Before') and basis_quality(L, 'After')

# Step 4: Check LLL conditions on the reduced basis
# Hint: check_lll_conditions(L)

Exercise 3 (Independent)

Problem: Use LLL to find a small integer linear combination of the columns of:

$$A = \begin{pmatrix} 105 & 821 & 377 \\ 231 & 57 & 610 \end{pmatrix}$$

that gives a short vector. Specifically:

1. Form the lattice generated by the columns of $A$ (i.e., $\{A\mathbf{x} : \mathbf{x} \in \mathbb{Z}^3\}$).

2. Apply LLL to find a reduced basis.

3. What is the shortest vector you find? What integer combination produces it?

4. Can you beat LLL by trying random combinations? How many random attempts does it take to find something as short?

# Exercise 3. Your code here

Summary

In this notebook we explored the LLL algorithm. Key takeaways:

• Gram-Schmidt orthogonalization provides the geometric backbone: it decomposes basis vectors into orthogonal components whose norms reveal the basis quality.

• LLL reduction requires two conditions: size-reduction ($|\mu_{i,j}| \le 1/2$) and the Lovász condition ($\|\mathbf{b}_i^*\|^2 \ge (\delta - \mu_{i,i-1}^2)\|\mathbf{b}_{i-1}^*\|^2$).

• The algorithm alternates between size-reducing (cleaning up projections) and swapping (fixing Lovász violations), converging in polynomial time.

• Quality metrics like orthogonality defect and Hermite factor quantify how "nice" a basis is.

• LLL guarantees $\|\mathbf{b}_1\| \le 2^{(n-1)/2} \cdot \lambda_1(L)$ — polynomial time, but exponential approximation factor.

• Applications include breaking knapsack crypto and finding integer relations — LLL is a universal tool for problems that can be cast as "find a short vector."

• Limitations: The approximation factor degrades exponentially with dimension, which is exactly what makes modern lattice-based cryptography possible.

Looking ahead: In notebook 08d, we introduce the Learning With Errors (LWE) problem — the computational hardness assumption behind Kyber/ML-KEM. The key insight: LWE problems live in dimensions large enough that even the best lattice reduction algorithms (LLL and its successors like BKZ) cannot find short enough vectors to break them.

Next: Learning With Errors