There are a few issues that one may encounter when attempting to generalize Lagrange's algorithm to higher dimensions. Most importantly, one needs to figure what is the proper way to swap the vectors around and when to terminate, ideally in in polynomial time. A rough sketch of how the algorithm should look like is
def LLL(B):d = B.nrows()i = 1while i<d:size_reduce(B)if swap_condition(B):i += 1else:B[i],B[i-1] = B[i-1],B[i]i = max(i-1,1)return B
There are two things we need to figure out, in what order should we reduce the basis elements by and how should we know when to swap. Ideally, we also want the basis to be ordered in a way such that the smallest basis vectors comes first. Intuitively, it would also be better to reduce a vector by the larger vectors first before reducing by the smaller vectors, a very vague analogy to filling up a jar with big stones first before putting in the sand. This leads us to the following size reduction algorithm:
def size_reduce(B):d = B.nrows()i = 1while i<d:Bs,M = B.gram_schmidt()for j in reversed(range(i)):B[i] -= round(M[i,j])*B[j]Bs,M = B.gram_schmidt()return B
Next, we need to figure a swapping condition. Naively, we want
for all . However, such a condition does not guarantee termination in polynomial time. As short basis vectors should be almost orthogonal, we may also want to incorperate this notion. Concretely, we want to be somewhat small for all pairs of , i.e. we may want something like
However, since , this condition is easily satisfied for a sufficiently long , which is not what we want. The key idea is to merge these two in some way and was first noticed by Lovász - named the Lovász condition:
It turns out that using this condition, the algorithm above terminates in polynomial time! More specifically, it has a time complexity of where we havebasis vectors as a subset of and is a bound for the largest norm of . ensures that the lattice vectors are ordered roughly by size and ensures the algorithm terminates.
This follows the proof provided by the authors of the LLL paper. We first prove that the algorithm terminates by showing it swaps the vectors finitely many times. Letbe the number of basis vectors as a subset of . Let be the volume of the lattice generated by at each step of the algorithm. We have . Now consider the quantity
This quantity only changes whenever some changes, i.e when swaps happen. Let's consider what happens when we swap and . Recall the Gram-Schmidt algorithm:
From this, see that when we swap and , is replaced by . Now using the Lovász condition, we see that we have, hence the value of must decrease by at least , i.e. the new is less than . All other must remain the same as the volume remains fixed when we swap basis vectors around. Hence at each swap, decreases by . This is why we need .Now we are left with showing is bounded from below then we are done.
Let be the length of the shortest (nonzero) vector in the lattice. We can treat as the volume of the lattice generated by. Let be the shortest vector in the lattice in . By using Minkowski's lattice point theorem, we have
(Note that the value of isn't particularly important, one can use a easier value like )
Hence we see that , and hence has a (loose) lower bound , meaning that there are at most swaps. Since at each iteration,either increases bywhen there is no swaps or decreases by at mostwhen there is swaps and ranges fromto, the number of time the loop runs must be at most , hence the algorithm terminates.
This proof also gives us a handle on the time complexity of the operation. Letis the length of the longest input basis vector. Since we have , and the algorithm loops times. The Gram-Schmidt orthogonalization is the most expensive part in the entire process, taking up arithmetic operations. By using classical algorithm for arithmetic operations, each takes time. From this, we deduce that the time complexity of the LLL algorithm is , a somewhat reasonable polynomial time algorithm.
Let be the output of the LLL algorithm, it turns out that we have the bound
which requires . Such bounds for the shortest vector will be elaborated in more detail in the section on reduced basis.
1) Implement the LLL in sage and experimentally verify that does indeed decrease byeach time.
2) Show that the time complexity analysis is correct, and indeed each loop takes at most operations.