2 search hits

Segment and strong segment LLLreduction of lattice bases
(2002)

Henrik Koy
Claus Peter Schnorr
 We present an efficient variant of LLLreduction of lattice bases in the sense of Lenstra, Lenstra, LovÂ´asz [LLL82]. We organize LLLreduction in segments of size k. Local LLLreduction of segments is done using local coordinates of dimension 2k. Strong segment LLLreduction yields bases of the same quality as LLLreduction but the reduction is ntimes faster for lattices of dimension n. We extend segment LLLreduction to iterated subsegments. The resulting reduction algorithm runs in O(n3 log n) arithmetic steps for integer lattices of dimension n with basis vectors of length 2O(n), compared to O(n5) steps for LLLreduction.

Fast LLLtype lattice reduction
(2004)

Claus Peter Schnorr
 We modify the concept of LLLreduction of lattice bases in the sense of Lenstra, Lenstra, Lovasz [LLL82] towards a faster reduction algorithm. We organize LLLreduction in segments of the basis. Our SLLLbases approximate the successive minima of the lattice in nearly the same way as LLLbases. For integer lattices of dimension n given by a basis of length 2exp(O(n)), SLLLreduction runs in O(n.exp(5+epsilon)) bit operations for every epsilon > 0, compared to O(exp(n7+epsilon)) for the original LLL and to O(exp(n6+epsilon)) for the LLLalgorithms of Schnorr (1988) and Storjohann (1996). We present an even faster algorithm for SLLLreduction via iterated subsegments running in O(n*exp(3)*log n) arithmetic steps.