Next: Theoretical Analysis
Up: No Title
Previous: Lattice Basis Reduction Algorithms
The Seysen Basis Reduction Algorithm
In 1990, Martin Seysen proposed a new method for performing lattice
basis reduction [38]. Seysen's basis reduction algorithm
(or just Seysen's algorithm) differs from the LLL algorithm and
its variants in that it considers all vectors in the lattice
simultaneously, and performs operations on those vectors which will
reduce the lattice according to some measure. Recall that the LLL
algorithm works locally on the lattice it is reducing; LLL will
only perform an operation on two vectors which are adjacent to each
other in the ordered lattice basis.
Seysen was motivated to create a new method for basis reduction by a
desire to find a better way to simultaneously reduce a lattice and its
reciprocal (or dual) lattice. If lattice L is defined by basis
vectors
,
then the dual lattice L^{*} of L
is defined by basis vectors
,
where

(2.1) 
Now consider what happens in the dual lattice when we perform a row
move on
and
in L. (A row move is any
operation which adds a constant multiple of one lattice basis vector to
another basis vector.) Let
,
where
.
We consider what changes must occur in the dual
lattice basis vectors
,
since
Equation 2.1 must hold at all times. For ,
we
find that:
For k = i, however, this is not the case:
Thus, when we add
to
in the basis of
lattice L, we must subtract
from
in
the basis of L^{*}. It is easy to see that if lattice L is reduced
with the LLL algorithm, the resulting reduced lattice may have a dual in
which some basis vector is quite large, as no attempt is ever made to
consider the size of the dual basis when row moves are being performed.
Seysen's algorithm attempts to choose row moves that reduce both the
lattice and its dual.
We now outline the basic operation of Seysen's algorithm. Let L and
L^{*} be a lattice and its dual which we wish to simultaneously reduce.
Let A and A^{*} be the associated quadratic forms of L and L^{*},
respectively:
The element a_{i,j} of matrix A is the inner product of the basis
vectors
and
of lattice L. Notice that A and A^{*}
are inverses of each other and are symmetric.
If L is the lattice defined by basis B, then any other basis B' of
L may be written as:
where
(i.e. T is an
integer matrix
with determinant 1). The quadratic form A' associated with B' may
similarly be derived from A:
For any quadratic form A, define the Seysen measure
S(A) as follows:

(2.2) 
A basis B is then Sreduced if:

(2.3) 
We suspect that it is computationally difficult to find the optimal
transformation matrix T for a given basis B.
Consider, however, the class of transformation matrices
defined by:
(The matrix U_{i,j} has exactly one nonzero entry. Matrix
has diagonal entries of 1 and exactly one nonzero
offdiagonal entry.) Rightmultiplying B by any
simply adds
times the
column of B to the
column of B. If the columns of B are the basis vectors
,
then
is simply the transformed basis
.
Since it is easy to perform calculations with
transformations, we focus our attention on
products of one or more
transformation matrices. It
can be shown that every
may be written as such a product:
We call a quadratic form S_{2}reduced if
Seysen suggests the following algorithm
for S_{2}reducing a quadratic form:
while (A is not S_{2}reduced)
do
choose i,j such that
with
let
let
where
denotes the nearestinteger function. This
procedure for S_{2}reducing a quadratic form is Seysen's basis
reduction algorithm.
To date, little has been proven concerning the performance of Seysen's
algorithm. There are no known bounds on the Seysen measure of an
S_{2}reduced basis (although bounds have been proven for Sreduced
lattice bases), nor on the length of the shortest nonzero vector in the
basis. The running time of Seysen's algorithm is clearly bounded if the
lattice basis consists of only integer vectors, but it is not known if
the algorithm even terminates for basis vectors with real coefficients.
However, preliminary experiments performed by Seysen on lattices of
dimension
suggest that this technique may be faster than the
LLL algorithm and yield bases with shorter vectors. Based on these
observations, a comprehensive investigation of theoretical and practical
aspects of Seysen's algorithm was undertaken. This chapter details the
results of our study of Seysen's basis reduction algorithm.
Section 2.1 below discusses the theoretical
underpinnings of Seysen's algorithm. Empirical tests performed with
various versions of the Seysen algorithm are detailed in
Section 2.2. Section 2.3
mentions some modifications which may be made to Seysen's algorithm
when the performance of the basic version breaks down. Finally,
Section 2.4 discusses possible extensions to
Seysen's algorithm.
Next: Theoretical Analysis
Up: No Title
Previous: Lattice Basis Reduction Algorithms
Brian A. LaMacchia
19991030