ABSTRACT
In this chapter we consider a modification of the exchange step of the original LLL algorithm: instead of transposing the vectors in positions k and k−1, we cyclically permute the vectors in positions i, i+1, . . . , k where i is the smallest index for which vectors i and k satisfy the exchange condition. In other words, we put vector k into position i, and put vectors i to k−1 into positions i+1 to k. (If i = k−1 then we have the exchange step of the original LLL algorithm.) This idea, called a deep insertion of vector k into position i, was introduced in 1994 by Schnorr and Euchner [127]. A more detailed exposition is given in Cohen [26], Section §2.6.2.
