08a-lattices-and-bases.ipynb

Kernel: SageMath 10.5

Lattices and Bases

Module 08a | Lattices and Post-Quantum Cryptography

The geometry of integer grids, and the surprising difficulty of finding short vectors.

Question: Imagine you're standing at the origin with two arrows (basis vectors). You can only move by adding or subtracting whole copies of these arrows. What points can you reach? And does it matter which arrows you start with?

By the end of this notebook, you'll see that the set of reachable points is a lattice, that the same lattice can arise from many different pairs of arrows, and that telling a "good" pair from a "bad" pair is the heart of post-quantum cryptography.

Objectives

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

1. Define a lattice as the set of all integer linear combinations of basis vectors

2. Visualize 2D lattices and their basis vectors in SageMath

3. Demonstrate that different bases can generate the same lattice via unimodular matrices

4. Compute the fundamental domain and its volume (= |det(B)|)

5. Distinguish "good" (short, orthogonal) from "bad" (long, nearly parallel) bases

Prerequisites

• Modules 01–06 (modular arithmetic, groups, rings, fields, number theory, elliptic curves)

• Basic linear algebra: vectors, matrices, determinants, linear independence

• A working SageMath installation (or CoCalc/SageMathCell)

Bridge from Modules 01–06: In those modules, cryptographic security came from number-theoretic problems — factoring (RSA), the discrete logarithm (Diffie-Hellman), and ECDLP (elliptic curves). Shor's algorithm can solve all of these on a quantum computer. We now turn to a fundamentally different source of hardness: the geometry of high-dimensional integer lattices. These problems are believed to resist even quantum attacks.

What Is a Lattice?

A lattice $\mathcal{L}$ is the set of all integer linear combinations of a set of linearly independent vectors $\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_n \in \mathbb{R}^m$:

$$\mathcal{L}(\mathbf{b}_1, \ldots, \mathbf{b}_n) = \left\{ \sum_{i=1}^{n} a_i \mathbf{b}_i \;:\; a_i \in \mathbb{Z} \right\}$$

The matrix $B$ whose rows are $\mathbf{b}_1, \ldots, \mathbf{b}_n$ is called a basis for the lattice. The lattice has rank $n$ and lives in ambient dimension $m$.

The key word is integer. Unlike a vector space (where coefficients can be any real number), lattice points are a discrete, countably infinite set — a regular grid of isolated points.

# A simple lattice: the standard integer grid Z^2
B_standard = matrix(ZZ, [[1, 0],
                          [0, 1]])
print('Standard basis:')
print(B_standard)
print(f'\nThis generates the familiar grid of all (a, b) with a, b in Z.')

# A more interesting basis
B = matrix(ZZ, [[3, 1],
                 [1, 2]])
print('Basis B:')
print(B)
print(f'det(B) = {B.det()}')
print(f'\nThe lattice L(B) = {{ a*(3,1) + b*(1,2) : a,b in Z }}')
print('This is NOT the standard grid, the points form a skewed pattern.')

Visualizing a 2D Lattice

Let's plot some lattice points. For each integer combination $a \mathbf{b}_1 + b \mathbf{b}_2$ with $a, b \in \{-k, \ldots, k\}$, we get a lattice point.

def plot_lattice(B, k=4, point_color='blue', point_size=30, arrows=True, arrow_color='red'):
    """
    Plot the lattice points generated by basis matrix B,
    using integer coefficients from -k to k.
    """
    b1 = vector(B[0])  # first basis vector (row 0)
    b2 = vector(B[1])  # second basis vector (row 1)
    
    # Generate all lattice points a*b1 + b*b2
    points = []
    for a in range(-k, k+1):
        for b in range(-k, k+1):
            p = a * b1 + b * b2
            points.append(p)
    
    # Plot the points
    G = point2d(points, color=point_color, size=point_size, zorder=5)
    
    # Draw basis vectors as arrows from the origin
    if arrows:
        G += arrow2d((0, 0), b1, color=arrow_color, width=2, arrowsize=3, zorder=10)
        G += arrow2d((0, 0), b2, color=arrow_color, width=2, arrowsize=3, zorder=10)
        # Label the basis vectors
        G += text(f'b1={tuple(b1)}', b1 + vector([0.3, 0.3]),
                  fontsize=10, color=arrow_color)
        G += text(f'b2={tuple(b2)}', b2 + vector([0.3, 0.3]),
                  fontsize=10, color=arrow_color)
    
    G.set_aspect_ratio(1)
    return G

# Plot the lattice with basis B = [[3,1],[1,2]]
B = matrix(ZZ, [[3, 1], [1, 2]])
G = plot_lattice(B)
G.show(title='Lattice L(B) with B = [[3,1],[1,2]]', axes=True, figsize=7)

Notice how the points form a regular pattern, but the grid is tilted and stretched compared to $\mathbb{Z}^2$. Each basis vector is an arrow from the origin, and every lattice point is an integer combination of these arrows.

Checkpoint: Look at the plot above. Is the point $(4, 3)$ in this lattice? Before reading on, try to find integers $a, b$ such that $a \cdot (3,1) + b \cdot (1,2) = (4, 3)$.

# Check: is (4, 3) in the lattice?
# We need to solve: a*(3,1) + b*(1,2) = (4,3)
# i.e., 3a + b = 4 and a + 2b = 3
B = matrix(ZZ, [[3, 1], [1, 2]])
target = vector(ZZ, [4, 3])

try:
    coeffs = B.solve_left(target)  # solve target = coeffs * B
    print(f'Coefficients: {coeffs}')
    print(f'Check: {coeffs[0]}*(3,1) + {coeffs[1]}*(1,2) = {coeffs[0]*B[0] + coeffs[1]*B[1]}')
    if all(c in ZZ for c in coeffs):
        print('All coefficients are integers => (4, 3) IS in the lattice!')
    else:
        print('Coefficients are not all integers => (4, 3) is NOT in the lattice.')
except:
    print('No solution exists.')

Common mistake: "A lattice is just a grid of evenly spaced points." Only if the basis is orthogonal! A general lattice has points at integer combinations of arbitrary linearly independent vectors. The spacing between points varies by direction — some directions are "dense," others are "sparse." This anisotropy is exactly what makes lattice problems hard.

Different Bases, Same Lattice

Here is the key insight that makes lattice cryptography work:

The same lattice can be described by many different bases. Some bases are "good" (short, nearly orthogonal vectors) and some are "bad" (long, nearly parallel vectors). Lattice cryptography hides secrets by publishing a "bad" basis while keeping a "good" one private.

When do two bases $B$ and $B'$ generate the same lattice? Precisely when $B' = U \cdot B$ for some unimodular matrix $U$ — an integer matrix with $\det(U) = \pm 1$.

# Start with a "good" basis
B_good = matrix(ZZ, [[3, 1],
                      [1, 2]])

# A unimodular matrix (det = +/-1)
U = matrix(ZZ, [[2, 3],
                 [1, 2]])
print(f'det(U) = {U.det()} => U is unimodular: {abs(U.det()) == 1}')

# Transform to a "bad" basis
B_bad = U * B_good
print(f'\nGood basis B:\n{B_good}')
print(f'\nBad basis B\' = U * B:\n{B_bad}')
print(f'\ndet(B)  = {B_good.det()}')
print(f'det(B\') = {B_bad.det()}')
print(f'|det| is the same: {abs(B_good.det()) == abs(B_bad.det())}')

# Visualize: SAME lattice, TWO different bases
B_good = matrix(ZZ, [[3, 1], [1, 2]])
U = matrix(ZZ, [[2, 3], [1, 2]])
B_bad = U * B_good

# Plot with the good basis (red arrows)
G1 = plot_lattice(B_good, k=5, point_color='blue', arrow_color='red')
G1.show(title='"Good" basis: short, nearly orthogonal', axes=True, figsize=7)

# Plot with the bad basis (dark green arrows)
G2 = plot_lattice(B_bad, k=5, point_color='blue', arrow_color='darkgreen')
G2.show(title='"Bad" basis: long, nearly parallel', axes=True, figsize=7)

Look carefully at the two plots. The dots are in exactly the same positions. Only the arrows (basis vectors) changed. The "good" basis has short, nearly perpendicular arrows that make the lattice structure obvious. The "bad" basis has long, nearly parallel arrows that obscure it.

Checkpoint: Can you verify that the bad basis generates the same points? Pick any lattice point from the first plot and express it using the bad basis vectors.

# Overlay both bases on one plot to make the comparison vivid
B_good = matrix(ZZ, [[3, 1], [1, 2]])
U = matrix(ZZ, [[2, 3], [1, 2]])
B_bad = U * B_good

b1_good, b2_good = vector(B_good[0]), vector(B_good[1])
b1_bad, b2_bad = vector(B_bad[0]), vector(B_bad[1])

# Lattice points (same for both bases)
points = [a * b1_good + b * b2_good for a in range(-5, 6) for b in range(-5, 6)]
G = point2d(points, color='blue', size=25, zorder=5)

# Good basis arrows (red)
G += arrow2d((0,0), b1_good, color='red', width=2.5, arrowsize=3, zorder=10)
G += arrow2d((0,0), b2_good, color='red', width=2.5, arrowsize=3, zorder=10)
G += text('good b1', b1_good + vector([0.4, 0.4]), fontsize=10, color='red')
G += text('good b2', b2_good + vector([0.4, 0.4]), fontsize=10, color='red')

# Bad basis arrows (dark green)
G += arrow2d((0,0), b1_bad, color='darkgreen', width=2.5, arrowsize=3, zorder=10)
G += arrow2d((0,0), b2_bad, color='darkgreen', width=2.5, arrowsize=3, zorder=10)
G += text('bad b1', b1_bad + vector([0.4, 0.4]), fontsize=10, color='darkgreen')
G += text('bad b2', b2_bad + vector([0.4, 0.4]), fontsize=10, color='darkgreen')

G.set_aspect_ratio(1)
G.show(title='Same lattice, two bases (red=good, green=bad)', axes=True, figsize=8)

Unimodular Equivalence

Let's formalize this. Two bases $B$ and $B'$ generate the same lattice if and only if there exists an integer matrix $U$ with $\det(U) = \pm 1$ (a unimodular matrix) such that:

$$B' = U \cdot B$$

Why $\det(U) = \pm 1$? Because:

• $U$ must be an integer matrix (so $B'$ has integer entries when $B$ does)

• $U$ must be invertible over the integers (so we can go back: $B = U^{-1} B'$)

• An integer matrix has an integer inverse iff $\det(U) = \pm 1$

The set of all $n \times n$ unimodular matrices forms a group called $\text{GL}_n(\mathbb{Z})$.

# Verify unimodular equivalence
B = matrix(ZZ, [[3, 1], [1, 2]])

# Several unimodular matrices
unimodulars = [
    matrix(ZZ, [[1, 1], [0, 1]]),   # shear
    matrix(ZZ, [[1, 0], [2, 1]]),   # another shear
    matrix(ZZ, [[0, 1], [1, 0]]),   # swap rows
    matrix(ZZ, [[2, 3], [1, 2]]),   # more complex
    matrix(ZZ, [[1, -1], [0, 1]]),  # negative shear
]

print(f'Original basis B (det = {B.det()}):\n{B}\n')
for i, U in enumerate(unimodulars):
    B_new = U * B
    print(f'U{i+1} (det={U.det()}):  B\' = {list(B_new[0])}, {list(B_new[1])}  '
          f'det(B\')={B_new.det()}')

print(f'\nAll have |det| = {abs(B.det())} => all generate the same lattice!')

# What if det(U) != +/-1? Then we get a DIFFERENT lattice.
B = matrix(ZZ, [[3, 1], [1, 2]])
U_not_unimodular = matrix(ZZ, [[2, 1], [1, 1]])  # det = 1... let's try det=2
U_bad = matrix(ZZ, [[2, 0], [0, 1]])              # det = 2
B_different = U_bad * B

print(f'det(U) = {U_bad.det()} (NOT unimodular)')
print(f'B\' = U*B:\n{B_different}')
print(f'det(B\') = {B_different.det()} != det(B) = {B.det()}')
print(f'\nB\' generates a DIFFERENT lattice (a sublattice of L(B)).')

# Visualize: original lattice in blue, sublattice in orange
b1, b2 = vector(B[0]), vector(B[1])
b1s, b2s = vector(B_different[0]), vector(B_different[1])

pts_orig = [a*b1 + b*b2 for a in range(-5,6) for b in range(-5,6)]
pts_sub = [a*b1s + b*b2s for a in range(-5,6) for b in range(-5,6)]

G = point2d(pts_orig, color='blue', size=30, zorder=5, legend_label='L(B)')
G += point2d(pts_sub, color='orange', size=50, zorder=6, legend_label='L(U*B), det(U)=2')
G.set_aspect_ratio(1)
G.show(title='Non-unimodular U => different (sub)lattice', axes=True, figsize=7)

The Fundamental Domain

The fundamental domain (or fundamental parallelepiped) of a lattice basis $B$ is the set:

$$\mathcal{F}(B) = \left\{ x_1 \mathbf{b}_1 + x_2 \mathbf{b}_2 : 0 \le x_i < 1 \right\}$$

It's the parallelogram (in 2D) spanned by the basis vectors. A crucial fact:

The volume of the fundamental domain = $|\det(B)|$, and this is the same for ALL bases of the same lattice.

This makes $|\det(B)|$ an invariant of the lattice itself, called the lattice determinant or covolume. Geometrically, it tells you the "density" of lattice points: larger determinant = sparser lattice.

def plot_fundamental_domain(B, fill_color='lightyellow', border_color='black', **kwargs):
    """
    Plot the fundamental parallelepiped of basis B along with lattice points.
    """
    b1, b2 = vector(RR, B[0]), vector(RR, B[1])
    origin = vector(RR, [0, 0])
    
    # The four corners of the parallelepiped
    corners = [origin, b1, b1 + b2, b2]
    
    # Plot the filled parallelogram
    G = polygon2d(corners, color=fill_color, edgecolor=border_color,
                  thickness=2, alpha=0.5, zorder=2)
    
    # Add lattice points and arrows
    G += plot_lattice(B, **kwargs)
    
    # Label the volume
    center = (b1 + b2) / 2
    G += text(f'Vol = |det(B)| = {abs(B.det())}', center,
             fontsize=12, color='black', fontweight='bold')
    
    return G

# Good basis
B_good = matrix(ZZ, [[3, 1], [1, 2]])
G1 = plot_fundamental_domain(B_good, fill_color='lightyellow', arrow_color='red')
G1.show(title=f'Fundamental domain (good basis), det={B_good.det()}',
        axes=True, figsize=7)

# Bad basis (same lattice!)
U = matrix(ZZ, [[2, 3], [1, 2]])
B_bad = U * B_good
G2 = plot_fundamental_domain(B_bad, fill_color='lightcyan', arrow_color='darkgreen')
G2.show(title=f'Fundamental domain (bad basis), det={B_bad.det()}',
        axes=True, figsize=7)

Both parallelograms have the same area ($|\det| = 5$), even though they look very different. The good-basis parallelogram is compact and fat; the bad-basis parallelogram is long and thin. But they tile the plane in the same way — one copy per lattice point, no gaps, no overlaps.

Crypto foreshadowing: The security of post-quantum schemes like Kyber (ML-KEM) and Dilithium (ML-DSA) reduces to lattice problems. An attacker is given a "bad" basis and must find short lattice vectors — essentially, recover a "good" basis. In 2D this is easy (the LLL algorithm, coming in notebook 08c). In 500+ dimensions, it is believed to be computationally infeasible even for quantum computers.

Measuring Basis Quality

How do we quantify whether a basis is "good" or "bad"? Two natural measures:

1. Vector lengths: $\|\mathbf{b}_1\|$ and $\|\mathbf{b}_2\|$. Shorter is better.

2. Orthogonality: the angle $\theta$ between $\mathbf{b}_1$ and $\mathbf{b}_2$. Closer to $90°$ is better.

The Hadamard ratio combines both:

$$\mathcal{H}(B) = \left( \frac{|\det(B)|}{\prod_{i} \|\mathbf{b}_i\|} \right)^{1/n}$$

This ratio is always between 0 and 1. A value of 1 means the basis is perfectly orthogonal. Values close to 0 indicate a "bad" basis with long, nearly parallel vectors.

def basis_quality(B):
    """Compute quality measures for a 2D lattice basis."""
    b1, b2 = vector(RR, B[0]), vector(RR, B[1])
    
    norm1 = b1.norm()
    norm2 = b2.norm()
    
    # Angle between vectors (in degrees)
    cos_theta = b1.dot_product(b2) / (norm1 * norm2)
    # Clamp to avoid numerical issues with acos
    cos_theta = max(-1, min(1, cos_theta))
    angle_deg = RR(arccos(cos_theta) * 180 / pi)
    
    # Hadamard ratio
    det_val = abs(B.det())
    hadamard = (det_val / (norm1 * norm2))^(1/2)
    
    return norm1, norm2, angle_deg, hadamard

B_good = matrix(ZZ, [[3, 1], [1, 2]])
U = matrix(ZZ, [[2, 3], [1, 2]])
B_bad = U * B_good

print('=== Good Basis ===')
n1, n2, angle, H = basis_quality(B_good)
print(f'  Vectors: {list(B_good[0])}, {list(B_good[1])}')
print(f'  Norms:   {n1:.3f}, {n2:.3f}')
print(f'  Angle:   {angle:.1f} degrees')
print(f'  Hadamard ratio: {H:.4f}')

print(f'\n=== Bad Basis ===')
n1, n2, angle, H = basis_quality(B_bad)
print(f'  Vectors: {list(B_bad[0])}, {list(B_bad[1])}')
print(f'  Norms:   {n1:.3f}, {n2:.3f}')
print(f'  Angle:   {angle:.1f} degrees')
print(f'  Hadamard ratio: {H:.4f}')

The good basis has shorter vectors, a wider angle, and a Hadamard ratio closer to 1. The bad basis has longer vectors, a narrower angle, and a Hadamard ratio closer to 0.

Checkpoint: If the Hadamard ratio is 1.0, what does the fundamental domain look like? (Answer: a rectangle — the basis vectors are perpendicular, and the parallelepiped degenerates to a rectangle.)

Beyond 2D: The Algebra Still Works

We can't visualize a 100-dimensional lattice, but the definitions are identical:

• A basis is an $n \times m$ matrix $B$ with linearly independent rows

• The lattice $\mathcal{L}(B) = \{ \mathbf{z} B : \mathbf{z} \in \mathbb{Z}^n \}$

• Two bases span the same lattice iff they differ by a unimodular matrix

• $|\det(B^T B)|^{1/2}$ gives the covolume (generalizing $|\det(B)|$ for square bases)

Cryptographic lattices typically have dimension $n = 256, 512,$ or $1024$. The intuitions from 2D — good vs. bad bases, finding short vectors, fundamental domain volume — all carry over, but the computational difficulty explodes with dimension.

# Higher-dimensional example: a 5D lattice
set_random_seed(42)
n = 5
B5 = random_matrix(ZZ, n, n, x=-10, y=11)

# Make sure it's full rank
while B5.det() == 0:
    B5 = random_matrix(ZZ, n, n, x=-10, y=11)

print(f'5D lattice basis ({n}x{n} matrix):')
print(B5)
print(f'\ndet(B) = {B5.det()}')
print(f'Covolume = |det(B)| = {abs(B5.det())}')

# Apply a unimodular transform
# Build one by composing elementary row operations
U5 = identity_matrix(ZZ, n)
U5[0] = U5[0] + 3 * U5[1]        # row 0 += 3 * row 1
U5[2] = U5[2] - 2 * U5[4]        # row 2 -= 2 * row 4
U5[3] = U5[3] + U5[1]            # row 3 += row 1
print(f'\nUnimodular matrix U (det={U5.det()}):')
print(U5)

B5_new = U5 * B5
print(f'\nNew basis B\' = U*B (det={B5_new.det()}):')
print(B5_new)
print(f'\nSame lattice? |det(B)| = |det(B\')| = {abs(B5_new.det())}: {abs(B5.det()) == abs(B5_new.det())}')

Exercises

Exercise 1 (Worked)

Given the basis $B = \begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix}$:

1. Compute the determinant and the Hadamard ratio.

2. Apply the unimodular matrix $U = \begin{pmatrix} 1 & -1 \\ 0 & 1 \end{pmatrix}$ to get $B' = UB$.

3. Verify that both bases generate the same lattice by checking that the point $(5, 7)$ has integer coordinates in both.

# Exercise 1: Worked solution

# Part 1: determinant and Hadamard ratio
B = matrix(ZZ, [[2, 1], [1, 3]])
print('Part 1:')
print(f'  B = {list(B[0])}, {list(B[1])}')
print(f'  det(B) = {B.det()}')
n1, n2, angle, H = basis_quality(B)
print(f'  ||b1|| = {n1:.4f}, ||b2|| = {n2:.4f}')
print(f'  Angle = {angle:.1f} degrees')
print(f'  Hadamard ratio = {H:.4f}')

# Part 2: apply unimodular transform
U = matrix(ZZ, [[1, -1], [0, 1]])
B_prime = U * B
print(f'\nPart 2:')
print(f'  U = {list(U[0])}, {list(U[1])}, det(U) = {U.det()}')
print(f'  B\' = U*B = {list(B_prime[0])}, {list(B_prime[1])}')
print(f'  det(B\') = {B_prime.det()}')

# Part 3: verify (5,7) is in both lattices
target = vector(ZZ, [5, 7])
coeffs_B = B.solve_left(target)
coeffs_Bp = B_prime.solve_left(target)
print(f'\nPart 3: Is (5,7) in the lattice?')
print(f'  Using B:  (5,7) = {coeffs_B[0]}*{list(B[0])} + {coeffs_B[1]}*{list(B[1])}')
print(f'    Integer coefficients? {all(c in ZZ for c in coeffs_B)}')
print(f'  Using B\': (5,7) = {coeffs_Bp[0]}*{list(B_prime[0])} + {coeffs_Bp[1]}*{list(B_prime[1])}')
print(f'    Integer coefficients? {all(c in ZZ for c in coeffs_Bp)}')

Exercise 2 (Guided)

Given the basis $B = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}$:

1. Plot the lattice and its fundamental domain.

2. Find a unimodular matrix $U$ such that $B' = UB$ has a higher Hadamard ratio than $B$.

3. Plot the new lattice to verify the points are the same.

Hint: Try simple shear matrices like $\begin{pmatrix} 1 & c \\ 0 & 1 \end{pmatrix}$ for small values of $c$.

# Exercise 2: Fill in the TODOs

B = matrix(ZZ, [[4, 1], [2, 3]])

# Part 1: Plot the lattice and fundamental domain
G = plot_fundamental_domain(B)
G.show(title='Exercise 2: Original basis', axes=True, figsize=7)

_, _, _, H_orig = basis_quality(B)
print(f'Original Hadamard ratio: {H_orig:.4f}')

# Part 2: TODO, Find a unimodular U that improves the Hadamard ratio
# Try: U = matrix(ZZ, [[1, c], [0, 1]]) for c = -1, 0, 1
# Compute basis_quality(U * B) for each and pick the best

# for c in [-2, -1, 0, 1, 2]:
#     U = matrix(ZZ, [[1, c], [0, 1]])
#     B_new = U * B
#     _, _, _, H_new = basis_quality(B_new)
#     print(f'  c={c}: Hadamard = {H_new:.4f}')

# Part 3: TODO, Plot the improved basis
# U_best = matrix(ZZ, [[1, ???], [0, 1]])
# B_improved = U_best * B
# G2 = plot_fundamental_domain(B_improved)
# G2.show(title='Exercise 2: Improved basis', axes=True, figsize=7)

Exercise 3 (Independent)

Create your own 2D lattice with a "deliberately bad" basis:

1. Start with the standard basis $I_2$ and apply 3–4 different unimodular transforms (compose them: $U = U_3 U_2 U_1$) to create a basis with Hadamard ratio below 0.2.

2. Plot your bad basis alongside the original to verify they generate the same lattice.

3. Compute the basis quality metrics and explain geometrically why the Hadamard ratio is so low.

4. Reflection: If someone gave you only the bad basis, could you easily recover the original? This is essentially the problem an attacker faces in lattice-based cryptography.

# Exercise 3: Your code here

Summary

Concept	Key idea
Lattice	The set of all integer linear combinations of basis vectors: $\mathcal{L}(B) = \{\mathbf{z}B : \mathbf{z} \in \mathbb{Z}^n\}$
Multiple bases	Two bases $B$ and $B'$ generate the same lattice iff $B' = UB$ for a unimodular matrix $U$ ($\det(U) = \pm 1$)
Fundamental domain	Its volume $
Good vs. bad bases	Good bases have short, nearly orthogonal vectors (high Hadamard ratio). Bad bases have long, nearly parallel vectors (low Hadamard ratio). Both generate the same points.
Crypto relevance	Lattice-based schemes publish a bad basis and keep a good one private. Finding a good basis from a bad one is computationally hard in high dimensions, and this hardness is believed to survive quantum computers.

Crypto connection: The NIST post-quantum standards ML-KEM (Kyber) and ML-DSA (Dilithium) rely on the hardness of lattice problems. In the next notebooks, we'll formalize these problems (SVP, CVP) and see how the LLL algorithm provides a partial solution — enough to break small lattices but not the large ones used in practice.

Next: The Shortest Vector Problem — why finding the shortest nonzero lattice vector is hard, and how SVP/CVP connect to cryptographic security.