Lattices

A lattice in Magma is a $\mbox{\bf Z}$-module contained in $\mbox{\bf Q}^n$ or $\mbox{\bf R}^n$, together with a positive definite inner product. The information specifying a lattice is a basis, given by a sequence of elements in $\mbox{\bf Z}^n$, $\mbox{\bf Q}^n$ or $\mbox{\bf R}^n$, and a bilinear product $(\cdot,\cdot)$, given by (v,w) = v M w^tr for a positive definite matrix M. Central to the lattice machinery in Magma is a highly optimized LLL algorithm. The LLL algorithm takes a basis of a lattice and returns a new basis of the lattice which is LLL-reduced which usually means that the vectors of the new basis have small norms. The Magma LLL algorithm is based on the FP-LLL algorithm of Schnorr and Euchner and the de Weger integral algorithm but includes various optimizations, with particular attention to different kinds of input matrices.