# Notation: b[1]..b[n] are vectors, bstar[1]..bstar[n] are their Gram-Schmidt vectors. # L = Z b[1] + .. + Z b[n], and Determinant(L) = product( |bstar[i]|, i=1..n). # The LLL algorithm computes a new basis for L by doing two types of operations: # (I) Size-reduction: b[k] := b[k] - r*b[j] for some j 0.51 then r := round(mu[k,j]); b[k] := b[k] - r*b[j]; # This step is called "Size-reduction" mu[k,j] := mu[k,j] - r fi od; bstar[k] := b[k] - add(mu[k,j]*bstar[j], j=1..k-1); B[k] := dot(bstar[k], bstar[k]); lprint("Current log2(G.S. lengths):", seq(evalf(log(B[i])/log(4),4),i=1..k)); # If we would swap b[k-1],b[k] then the new bstar[k-1] would be: # bstar[k] + mu[k,k-1]*bstar[k-1] and the new B[k-1] would be: newB_k_1 := B[k] + mu[k,k-1]^2*B[k-1]; # If the new B[k-1] is smaller than the current B[k-1] then swapping # makes progress. Only swap if it makes at least MinProgress: if newB_k_1 < delta * B[k-1] then b[k-1], b[k] := b[k], b[k-1]; k := k-1 # Property L holds. else k := k+1 # Property L holds. fi od; [seq(b[i], i=1..n)] # k>n so b[1]..b[n] are LLL-reduced end: # In a typical input, the first couple of vectors have large Gram-Schmidt # length while later vectors have small Gram-Schmidt length. With each swap, # the LLL algorithm moves G.S. length towards later vectors. L := [ [ 1, 0, 0, 0, 0, 0, 0, 10000000000, 0], [ 0, 1, 0, 0, 0, 0, 0, -5119504669, -11699359581], [ 0, 0, 1, 0, 0, 0, 0, -11066568655, 11978985199], [ 0, 0, 0, 1, 0, 0, 0, 19680180515, 6814529537], [ 0, 0, 0, 0, 1, 0, 0, -2102714461, -26513252424], [ 0, 0, 0, 0, 0, 1, 0, -29942321727, 16033513214], [ 0, 0, 0, 0, 0, 0, 1, 34087169230, 26822234281] ]; # In this example, the initial log2(G.S. lengths) are: # 33.22 33.45 1.118 0.832 0.831 0.7575 0.7345 # Each swap moves G.S. length forward (from b[k-1] to b[k] for some k). # The log2(G.S. lengths) in the output are: # 6.635 10.52 10.74 10.82 10.68 10.74 10.80 # Note: LLL can not always find the shortest vector (that's NP-hard) # but when the first vector has the smallest G.S. length then we found # the shortest non-zero vector in L. MyLLL(L);