I want to know is there is an efficient way to figure out whether or not a ( underdetermined) system of non-linear equations have a solution over a finite field of large prime order. The equations are non-linear, however, the degree of each unknown in any equation is at most 1. Any guidance or a reference to a resource which might be of help would be appreciated.

I know that one way is to generate an ideal of those equations and add equations of the form x_i^q – x_i=0 for each unknown x_i where q is the order of the field. But this will take forever for large q.

Any help would be appreciated.

Thanks, Adam

To be more precise, the equations I have look something like the following: There are 9 unknown (x_1, ..., x_9). I want to show that there is a solution for any given a,b,c,d,e,f,g,h,i \in F_q

g*x_6 + e*x_8 = e - b*x_3*x_1 - c*x_3 - i*x_1

d*x_6 + f*x_8 = f - a*x_3 - h*x_1

g*x_7 - i*x_8 = - b*x_3*x_2 - i*x_2

g*x_9 - c*x_8 = - b*x_5*x_1 - c*x_5

d*x_9 - a*x_8 = - a*x_5

d*x_7 - h*x_8 = - h*x_2

b*x_8 = b*x_5*x_2

x_4 = 0

Hmmm, the system of equations I am interested in solving is more complex than the toy example above I used as an example but again the criteria about the degree of the polynomials is the same.

I do not want to do it manually. Is there a way to get, for instance, Sage or Singular to find the solutions in the field F_q itself? I am not interested in solutions in the Algebraic closure of the field, i.e. I am only interested in the solutions which are elements in F_q itself. I got to the point where I computed the groebner basis for the ideal I generated by my system of equations in the polynomial ring over F_q and I test that 1 is not in the ideal I which implies the system has a solution. Does this mean the solutions are by default guaranteed to exist in F_q? If I try to add the Field polynomials to the system, Sage hangs even for a toy example using small $q$, e.g., q=127.

Thanks