Basis Perturbation

Suppose that we want to find many short vectors in a given lattice L. A situation where we may wish to do this is the following one. We are given a vector a that possesses more than one integer relation--let us assume that by running an integer relation algorithm on a we have discovered k linearly independent relations c⁽¹⁾, ..., c^(k). Let L be the lattice spanned by $\{c^{(1)}, ..., c^{(k)}\}$; then every element from L again is an integer relation for a. Short vectors are usually easier to analyze for patterns, hence we might wish to have a larger collection of short vectors from L.

Let $SL(n,\mathbb Z)$ be the special linear group of the $n\times n$ matrices over $\mathbb Z$with determinant equal to 1, where n is the dimension of the lattice L. If B is a basis for L, then for any $M\in SL(n,\mathbb Z)$, the image $M\cdot B$ is also a basis for L. By running the basis reduction algorithm on many different bases of Lwe increase our chances of finding more short vectors of L. A method for generating the matrices from $SL(n,\mathbb Z)$ with some degree of randomness is needed here; in our computations we have chosen to use matrices obtained as products of the type $\prod_{k=1}^m M^{(k)}$, where each M^(k)is of the form of the $n\times n$ identity matrix with an $SL(2,\mathbb Z)$ submatrix inserted at the intersections of the i-th and j-th row and column, for two randomly chosen $i,j\in\{1,2,\ldots,n\}$.