ABSTRACT
In this chapter we consider a modification of the LLL algorithm in which the input vectors are allowed to be linearly dependent. This algorithm, called the modified LLL algorithm, or MLLL algorithm for short, was introduced by Pohst [118] in 1987. In the simplest case, we are given m vectors x1, x2, . . . , xm in an (m−1)-dimensional lattice L ⊂ Rn where we assume that the first m−1 vectors x1, x2, . . . , xm−1 are linearly independent. This special case, which is essentially the inductive step in the general case, is discussed in Pohst and Zassenhaus [119], §3.3. A similar algorithm is discussed in Cohen [26], §2.6.4. One drawback of these original presentations is the large number of “goto” statements, which make the logical structure of the algorithm difficult to follow. The discussion in this chapter follows the more structured version of Pohst’s original algorithm given by Sims [131], §8.7; his single “goto” statement is easily replaced by a Boolean variable. Other closely related algorithms are presented in Gro¨tschel et al. [51], §5.4; Buchmann and Pohst [20]; Schnorr and Euchner [127]; and Hobby [63].
