ABSTRACT
This chapter discusses Schnorr’s paper [123] which introduced a one-parameter family of lattice basis reduction algorithms interpolating between the LLL algorithm [88] and Kannan’s algorithm [70, 71] for a Hermite-reduced basis. For an n-dimensional lattice L ⊂ Zn and a fixed integer k ≥ 2, Schnorr’s algorithm repeatedly applies Hermite reduction to blocks of length k in the lattice basis b1,b2, . . . ,bn ∈ Zn. For k = 2, the algorithm is equivalent to LLL reduction; for k = n, the algorithm is equivalent to Hermite reduction. Schnorr’s algorithm outputs a (nonzero) vector x ∈ L for which
|x|2 ≤ (6k2)n/kΛ1(L)2, where Λ1(L) is the first minimum of L. If B is an upper bound for |b1|2, |b2|2, . . . , |bn|2 then the complexity of Schnorr’s algorithm is given by
O ( n2(kk/2+o(k) + n2) logB
) ,
arithmetic operations on integers with O(n logB) binary digits. The basic idea of the LLL algorithm is to repeatedly perform the Gaussian
algorithm on sublattices of dimension 2. The output of the Gaussian algorithm is a Hermite-reduced basis of a 2-dimensional lattice (Exercise 12.1). The basic idea of Schnorr’s algorithm is that this strategy can be generalized, using Kannan’s algorithm for Hermite reduction, to repeatedly compute a Hermitereduced basis for sublattices of dimension k, where k is any integer ≥ 2.
