Solving Non-Linear Equations over a Finite Field of a Large Prime Order

Question

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

Answer 1

First a general comment: if you have some information about the geometry of the variety that the equations define, you can apply the Weil bounds in some form and show that there is a solution.

If the unknowns only appear to the first order, then you have something like $fx_n + g =0$, where $f,g$ don't involve $x_n$ and all you need is a point where $f \ne 0$ to solve for $x_n$. The total number of zeros of $f$ do not exceed $(\deg f)q^{n-2}$ if $f$ depends on $n-1$ variables. But again you say the degree in each variable is at most one, so $\deg f \le n-1$. So, if $q > n$ there is always a point with $f \ne 0$ and you can solve for $x_n$.

Edit: This needs more detail. Eliminate $x_n$ from all but one equation. Now, do what I had before to induct on $n$.