Lattices

Every code listing from this chapter of Applied Post-Quantum Cryptography — 9 in total, 9 runnable here. Edit any cell and press Run.

The book's snippets build on each other down the chapter, but a Sage Cell kernel runs one cell and keeps no state afterwards, so each cell replays the earlier listings with apqc_book. That call is the only thing added to the book's own code.

← the playground

Listing 1 — Sage experiment: generate a two-dimensional lattice

Listing 2 — Sage experiment: two different bases

Listing 3 — Sage experiment: determinant

Listing 4 — Sage experiment: shortest vector

Sage provides built-in lattice tools. A lattice object can be created directly from an integer matrix as follows:

Listing 5 — Sage experiment: shortest vector

Once the lattice is defined, the shortest vector can be computed with a single command:

Listing 6 — Experiment 1: enumerating the lattice

Generate a finite window of the lattice Λ(b₁,b₂) and confirm that it is a discrete grid of points, not a continuous span.

Listing 7 — Experiment 2: the determinant is a basis invariant

Compute the lattice determinant detΛ = |det B| for several bases of the same lattice, each obtained by left-multiplying B by a unimodular matrix U ∈ GL_n(ℤ) (an integer matrix with det U = ± 1).

Listing 8 — Experiment 3: good bases versus bad bases

A single lattice admits both near-orthogonal (“good”) and highly skewed (“bad”) bases. Contrast the two, and quantify the skew through the orthogonality defect ∏_i ‖ b_i‖ / detΛ.

Listing 9 — Experiment 4: the shortest vector is a lattice invariant

Compute the shortest nonzero vector for several distinct bases of the same lattice and confirm that its length is a property of the lattice, not of the chosen basis.