CoCalc -- LLL_for_generating_unimodular

LLL Play Files

Project: Algebraic Algorithms Exploring LLL

Path: backup_files / LLL_for_generating_unimodular_matrices.sagews

Views: ¹⁹⁸

The act of performing lattice reduction is essentially applying a sequence of elementary operations to a matrix. (Swaps and add a multiple of one row to another.)

These elementary operations can be encoded as simple matrices of determinant 1.

A product of elementary unimodular matrices will be a more complicated unimodular matrix. Sometimes you want such a thing.

#This block of code will generate a unimodular U with entries of size roughly 2^bits
bits = 4
d = 6
C = 2^bits
X = Matrix(ZZ, d, 1, [randint(1,2^(bits*d-1))for i in range(d)])
M = identity_matrix(d).augment(X)
Res = M.LLL()
U = Res.submatrix(0,0,d,d)
print M
print U
print U.det()

[      1       0       0       0       0       0 8103237]
[      0       1       0       0       0       0 3763685]
[      0       0       1       0       0       0  680748]
[      0       0       0       1       0       0 2414985]
[      0       0       0       0       1       0 4849232]
[      0       0       0       0       0       1 4962043]
[  1  -3  -2  -4   6  -3]
[ -2   3  -4   9  -7   4]
[  9  -2  -5   3  -2 -12]
[ -7  14  -5  -5   3   1]
[  6   5 -14  -6 -11   2]
[ -5  -7  -5   5  12   0]
-1

The size of the first row in (M), let's say (|\vec{r_1}|), will be pretty close to the volume of the lattice. The act of lattice reduction will smooth out the Gram-Schmidt lengths of each vector from what is effectively one large G-S length to ( d ) vectors each of size ( {|\vec{r_1}|}^{1/d} ).

RR = RealField(30)
G,mu = M.gram_schmidt()
for i in range(d):
    print RR(abs(G.row(i)))

G,mu = Res.gram_schmidt()
for i in range(d):
    print RR(abs(G.row(i)))