Lattice reduction is a general-purpose tool: give it a basis and it returns short vectors. The craft is in the embedding, the choice of basis that makes the answer to your problem one of those short vectors. These guides grow from a three-dimensional example to systems with a hundred unknowns. Every example runs with the g6k-rs recipes, and reading the basis and LLL chapters first will help.

7.1

Embedding basics

The five-step recipe, determinant and Gaussian heuristic, and a first embedding you can check by hand.

Dimension 3
7.2

Integer relations

Recover the minimal polynomial of an algebraic number from its decimal digits, and choose the scaling factor that makes it work.

Dimension 5–9
7.4

Closest vectors by Kannan embedding

Turn a closest-vector problem into a shortest-vector problem with one extra coordinate, and compare it with Babai decoding.

Dimension 20–40
7.5

Short solutions of Ax = b

Kernel lattices, homogenization, sub-dimension choice and progressive BKZ with sieving on larger instances.

Dimension 40–100