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
gx_6 + ex_8 = e - b*x_3*x_1 - cx_3 - ix_1
dx_6 + fx_8 = f - ax_3 - hx_1
gx_7 - ix_8 = - b*x_3*x_2 - i*x_2
gx_9 - cx_8 = - b*x_5*x_1 - c*x_5
dx_9 - ax_8 = - a*x_5
dx_7 - hx_8 = - h*x_2
bx_8 = bx_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