LLL_for_working_modulo_stuff.sagews

So if you want to find relations between objects but modulo something (a prime, prime power, a polynomial) then set up an identity matrix for the non-modulus objects and no weights for the modulus

values = vector([randint(-10^5,10^5) for i in range(5)])
weights = vector([2, 0, -3, 0, 1])
modulus = 10^6
target = values * weights % modulus
target

46965

L = list(values)
L.append(-target)
C = 2^20
M = identity_matrix(6).augment(C*vector(L))
print M

[ 1 0 0 0 0 0 -39900413952] [ 0 1 0 0 0 0 -32697745408] [ 0 0 1 0 0 0 -75750178816] [ 0 0 0 1 0 0 -8391753728] [ 0 0 0 0 1 0 -98203336704] [ 0 0 0 0 0 1 -49246371840]

M = M.insert_row(M.nrows(),[0 for i in range(M.nrows())] + [C*modulus])
M[5,5] *= 1000
print M

[ 1 0 0 0 0 0 -39900413952] [ 0 1 0 0 0 0 -32697745408] [ 0 0 1 0 0 0 -75750178816] [ 0 0 0 1 0 0 -8391753728] [ 0 0 0 0 1 0 -98203336704] [ 0 0 0 0 0 1000 -49246371840] [ 0 0 0 0 0 0 1048576000000]

M.LLL()

[ 6 -1 0 -5 9 0 0] [ -1 -12 4 -8 2 0 0] [ -5 12 10 0 1 0 0] [ 12 5 3 -10 -8 0 0] [ -8 6 -19 -9 6 0 0] [ 2 0 -3 0 1 1000 0] [ 0 0 4 -1 -3 0 1048576]

Check it out, we recovered the weights!

Sometimes we don't get back our weights... That's ok, this search space is large and it is part of why shortest vector is NP-hard. What we can say is that other combinations that match the target will be integer combinations of the early rows added to the target row. If we up the size of (C) (and possibly the modulus if that is an option) then our odds go up.

The following doesn't accomplish much algorithmically, it's more of a concept that is useful when you want LLL for algebraic number fields

R.<x> = PolynomialRing(ZZ)
f = R.random_element(5)

f

x^5 - 2*x^4 - x^3 + 3*x^2 - x + 5

coeffs = f.coeffs()

C = 10^5
coeffs[-1] *= -C

coeffs

[5, -1, 3, -1, -2, -100000]

X = Matrix(ZZ, 1, len(coeffs), coeffs)

I = identity_matrix(len(coeffs))

M = I.augment(X.transpose()).transpose()
M[len(coeffs)-1, len(coeffs)-1] *= C
UM = identity_matrix(M.nrows()).augment(M)
UM[len(coeffs), len(coeffs)] = 0
print UM

[ 1 0 0 0 0 0 0 1 0 0 0 0 0] [ 0 1 0 0 0 0 0 0 1 0 0 0 0] [ 0 0 1 0 0 0 0 0 0 1 0 0 0] [ 0 0 0 1 0 0 0 0 0 0 1 0 0] [ 0 0 0 0 1 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 1 0 0 0 0 0 0 100000] [ 0 0 0 0 0 0 0 5 -1 3 -1 -2 -100000]

UM.LLL()

[ 1 0 0 0 0 0 0 1 0 0 0 0 0] [ 0 1 0 0 0 0 0 0 1 0 0 0 0] [ 0 0 1 0 0 0 0 0 0 1 0 0 0] [ 0 0 0 1 0 0 0 0 0 0 1 0 0] [ 0 0 0 0 1 0 0 0 0 0 0 1 0] [ -2 0 -2 0 1 1 0 3 -1 1 -1 -1 0] [ 0 0 0 0 0 1 0 0 0 0 0 0 100000]