Is there an efficient algorithm to find all zeros of systems of multivariate polynomial equations over a finite field?

Question

I want my computer to solve large systems of multivariate polynomial equations over a finite field. The field is $\mathbb F_p$, where $p$ is a prime number. I heard that there is an algorithm using reduced Groebner bases but they say it takes too long. Are there any better algorithm when the given field is finite?

Answer 1

I quick description of what the Grobner basis is doing that is too long for a comment.

Background fact: The typical way to go about finding zeros of a one dimensional system uses what is called a companion matrix. Given a polynomial $f(x)$ of degree $d$, you make a vector of length $d$ representing a generic polynomial of degree $d-1$ (each spot is a monomial), and find the matrix $M$ that represents the multiplication by $x$ operator on the vector modulo ${f(x)}$. The eigenvalues of $M$ are then the roots of $f$.

The idea behind a Grobner Basis is to build the same type of matrix, but it is a little more complicated in higher dimensions. In general, say you have polynomials $f_1,...,f_n$. You need to find a set of monomials $V$ such that you can multiply any of the monomials by some $x_i$, mod out by your list of polynomials and any monomial multiple of those polynomials, and reduce the answer back into $V$. You can then find $M_i$ as the matrix that represents the multiplication by $x_i$ operator on $V$ modulo your polynomial. Simultaneously finding the eigenvalues of the $M_i$ then gives the zeros.

The point behind computing a reduced Grobner Basis is that it gives you $V$, and makes computing the $M_i$ easy.

However, this is slow for multiple reasons.

1. Finding V is slow. It basically comes down putting an ordering on the monomials and then doing long division on your polynomials until the monomials are as small as you can get them. So if you have any very simple polynomials (especially ones that only have a few variables) that will be very useful as they can hopefully reduce the others faster. But because you use monomial multiples of the polynomials to reduce, your reduced polynomials can end up with lots of monomials that weren't even in the original polynomials. So the size of $V$ can end up huge, regardless of how many monomials are in the original set.

2. Finding the eigenvalues will be slow if $V$ is big. If $V$ has $n$ elements, then $M$ is an $n\times n$ matrix. With 84 variables you could easily end up with millions of monomials in $V$, which would make the eigenvalue problem impossible on a typical computer.

Conclusion: It is possible it will work but unlikely for that many variables, unless you get really nice cancelation. Even then, depending on what software you use to calculate the Grobner Basis it might not reduce things optimally and so could take longer than needed.

Answer 2

When $p = 2$ even determining whether such a solution exists is equivalent to SAT, the Boolean satisfiability problem (where multiplication = AND and addition = XOR), which is NP-complete. So the existence of an efficient algorithm to determine even whether solutions exist in this case is equivalent to P = NP.