Next: Applications Up: Integer Relation Algorithms Previous: Finding Minimal Polynomials

## 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(1), ..., c(k). Let L be the lattice spanned by ; 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 be the special linear group of the matrices over with determinant equal to 1, where n is the dimension of the lattice L. If B is a basis for L, then for any , the image 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 with some degree of randomness is needed here; in our computations we have chosen to use matrices obtained as products of the type , where each M(k)is of the form of the identity matrix with an submatrix inserted at the intersections of the i-th and j-th row and column, for two randomly chosen .

Next: Applications Up: Integer Relation Algorithms Previous: Finding Minimal Polynomials
Agnes Szanto
2000-05-10