> < ^ From:

< ^ Subject:

Dear Mrs. and Mr. Forum,

Jaroslav Gurican writes

does LLL-algorithm (or some of modifications) offer possibility to

decide memebship (of some element in Z^n in the given lattice?

I need some bibliography on this topic, if possible.

(I would like to avoid excursions to Preburger arithmetic).

I do not see that the LLL algorithm can be used as a general method to

decide membership in lattices. One could think of adding the element

in question to a lattice basis, reduce the vectors using the LLL algorithm,

and then look at the transformation matrix whether the new vector has been

expressed in terms of the old basis. But if this is not the case then of

course this doesn't prove that the vector is not contained in the lattice.

(On the other hand, I cannot prove that the LLL algorithm cannot be used

to decide membership.)

A possibility of testing membership would be to transform the matrix whose

rows form a lattice basis into diagonal form, and to apply the column

transformations to the element in question; then membership can be read

off easily. The problem with this is the ``entry explosion'' during the

process of diagonalizing the matrix.

Kind regards

Thomas Breuer

(sam@math.rwth-aachen.de)

> < [top]