Solving a system of equations over finite fields with integer coefficients

savecancel

It looks like under "polynomial equivalent" of a number $n$ you understand the element of K with coefficients being the binary digits of $n$. If so, here is a simple conversion functions forth and back :

K.<x>= GF(2^4, modulus=x^4+x+1)
to_K = lambda n: K(ZZ(n).digits(2))
to_Z = lambda f: f.polynomial().change_ring(ZZ)(2)

Here to_K(5) gives x^2+1, to_K(3) gives x+1, and so on.

For a matrix / vector with numerical coefficients, you can easily convert them all to K at once as in the following example:

M = Matrix( [[2,5],[3,6]] )
b = vector( [3,4] )

M_ = M.apply_map(to_K)     # matrix with elements from K
b_ = b.apply_map(to_K)     # vector with elements from K

Then you can solve the system over K and convert elements of the solution back to integers as in

(M_ \ b_).apply_map(to_Z)