0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How large exactly is the system? $\endgroup$ – Erik Parkinson Jan 4 at 6:33
  • $\begingroup$ @Erik It can be arbitrarily large. But I would be happy if I can solve a system having 84 variables and 156 equations over $\mathbb F_5$ in a reasonable time. But ultimately the algorithm has to handle systems having arbitrarily many (but finite) number of variables and polynomials over arbitrary $\mathbb F_p$ ($p$ is a prime number). So the computational complexity shouldn't grow too fast. $\endgroup$ – zxcv Jan 4 at 6:43
  • $\begingroup$ And what degree polynomials are they typically? I can confirm that creating a reduced Groebner Basis will definitely take to long, even with just a few variables that is slow. I have a lot of experience with this problem over the reals, but not in a finite field so I'll have to think about it. $\endgroup$ – Erik Parkinson Jan 4 at 6:49
  • $\begingroup$ @Erik Typically degrees aren't that big. In the special case I mentioned above (system with 84 variables and 156 equations), all the polynomials have the highest total degree of 2, 4, and 6. Degrees aren't affected by the number of equations and variables, and it is also not affected by the value of $p$ in $\mathbb F_p$. So I think degrees will almost always be this small. $\endgroup$ – zxcv Jan 4 at 7:17
  • $\begingroup$ @Erik One more thing. The system can be over the real or even complex numbers. But I set the system to be over finite fields because I thought there would be a faster algorithm for finite fields. If there is a good algorithm over infinite fields, that is also okay. And I don't know if this would help, but I'm looking for all solutions in $\{0, 1\}^n$, no matter what the given field is. There is no need to find solutions outside $\{0, 1\}^n$. $\endgroup$ – zxcv Jan 4 at 7:21
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.