Module lattice

Integer lattices and algorithms.

Structs

AffineLattice

A lattice that is offset from the origin by a vector. Mathematicians would call this a lattice coset.

Lattice

A “lattice”, i.e. the span of a set of vectors. This can never be empty because it always contains the zero vector even if Lattice::basis has zero rows. The matrix always stores the ambient dimension (the number of columns) even if there are zero rows.

Traits

WorkingType

Lattice algorithms are possibly internally working with a different ring. These rings need to implement this.

WorkingTypeFor

This trait facilitates the conversion between the ring of the lattice and the ring used internally.

Functions

cvp_nearest_plane

Approximates the CVP using Babai’s nearest plane algorithm. The return value is a pair of the vector and the vector of coefficients of that vector if compute_coefficients is true. Otherwise the second element of the pair is an empty vector.

cvp_planes

Solves the CVP exactly.

cvp_rounding

Approximates the CVP using Babai’s rounding technique. The returns value is a vector of the coefficients of the linear combination of the basis vectors, so if you want the actual point, you still have to matrix multiply with the basis matrix. In practice, it is a good idea to reduce the basis (e.g. using LLL) so that the approximation is good.

gram_schmidt

Gram-Schmidt of the rows of the matrix a. The rows will span the same subspace as the original rows, even if they are not linearly independent. The rows of the result are not normalized. Call gram_schmidt_orthonormal if you want that.

gram_schmidt_orthonormal

Gram-Schmidt of the rows of the matrix a. The rows of the result are normalized. Call gram_schmidt if you don’t want that. This functions requires that the rows are linearly independent (unlike gram_schmidt).

lll

Performs LLL basis reduction using rational numbers.

rq_decomposition

Computes the RQ-decomposition (row QR-decomposition) of a matrix. Returns a lower triangular matrix R and an orthogonal matrix Q, such that R * Q = A.

size_reduce

Size reduce the basis. This essentially is Gram-Schmidt but rounding the coefficients to integers.