# Solving a system of equations over finite fields with integer coefficients

I want to solve a system of equations in $GF(2^4)$, with irreducible polynomial being $x^4 + x + 1$. The field is defined as follows:

K.<x>= GF(2^4, modulus=x^4+x+1)


Now suppose our equations are in the form $2u + 5v = 3$. Can I use this equation directly or should I substitute the polynomial equivalent of the numbers? That is, replace $2$ with $x$ and $5$ with $x^2 + 1$ and $3$ with $x + 1$ which gives us:

u*x + v*x^2 + v = x + 1


If so, this is a huge overhead for me. Is there an alternative way?

edit retag close merge delete

Sort by » oldest newest most voted

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)

more

Yes, I meant the decimal equivalent of the binary representation of field elements. It was my mistake, I should have made it clear. Thank you for your attention to this matter. I’m really grateful for making the problem easier for me.

( 2023-10-27 11:35:55 +0200 )edit