from random import randint
from tqdm import tqdm
from sage.rings.polynomial.msolve import variety as msolve_variety

F = GF(3301, names=("z", ))

f_a = list(F)

# m = 32
# n = 80

# m = 44
# n = 112

# m = 72
# n = 184

# m = 8
# n = 20

# m = 2
# n = 5

m = 44
n = 112


print("vars: ", n)
print("eqns: ", m)

print("actual vars: ", n - m)
print("actual eqns: ", m + m)

O = random_matrix(F, (n - m), m)

output = ""
poly_m = []

z = zero_matrix(F, m, (n - m))

for i in tqdm(range(m)):

    P1 = random_matrix(F, (n - m), (n - m))

    for j in range(0, len(P1.rows())):
        for k in range(0, j): P1[j, k] = 0
    P2 = random_matrix(F, (n - m), m)
    P3 = -O.T * P1 * O - O.T * P2

    for j in range(0, len(P3.rows())):
        for k in range(j+1, len(P3.rows())):
            P3[j, k] += P3[k, j]
            P3[k, j] = 0

    for i in P1:
        for j in i:
            output += hex(f_a.index(j))[2:]

    for i in P2:
        for j in i:
            output += hex(f_a.index(j))[2:]

    for i in P3:
        for j in i:
            output += hex(f_a.index(j))[2:]

    P = block_matrix([ [P1, P2], [z, P3]])
    poly_m.append(P)

v = matrix(F, n, 1, [randint(0, 1) for i in range(n)])

oil_basis = block_matrix(F, 2, 1, [O, identity_matrix(F, m)])

var_list = ','.join([f'x{i}' for i in range(n - m)])
R = PolynomialRing(F, var_list)


value = zero_matrix(R, n, 1)
hint = zero_matrix(R, n, 1)
hint2 = zero_matrix(R, n, 1)

for i in oil_basis.columns():
  value += F.random_element() * matrix(F, n, 1, list(i))
  hint += F.random_element() * matrix(F, n, 1, list(i))
  hint2 += F.random_element() * matrix(F, n, 1, list(i))

print(value)

print()
print(n - m)

print()
for i in range(n - m):
  value[i] = R(f'x{i}')

polys = []
for i in poly_m:
  polys.append((value.T * i * value)[0][0])
  polys.append((value.T * (i + i.T) * hint)[0][0])
  polys.append((value.T * (i + i.T) * hint2)[0][0])

I = R.ideal(*polys)



print(msolve_variety(I, F, proof=False))