# To solve large systems of multivariate polynomial equations

Nicolas Courtois et al. proposed the eXtended Linearization(XL) method to solve the systems of multivariate polynomial equations and analyzed the time complexity.

• Polynomial when the number of (random) equations $m \ge \epsilon n^2$, and this for all $\epsilon>0$, here $n$ is the number of variables.
• Subexponential if $m > n$ even by a small number.

But they didn't describe the size of $m$ and $n$. So my questions is that for a set of equations with the highest degree 3, how big can $m$ and $n$ be?

Reference:

Courtois N, Klimov A, Patarin J, et al. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations[M]// Advances in Cryptology — EUROCRYPT 2000. Springer Berlin Heidelberg, 2000:392-407.

• number of equations, $m$, can be arbitrarily large
• number of variables as well
• Thanks for your answer and edit. Considering the computing capacity of modern computer, can m and n still be arbitrarily large?
– haik
Jun 8, 2016 at 15:17
• @haik yes, but you will take arbitrarily large time to solve the problem Jun 8, 2016 at 15:18
• So how about within an acceptable time?
– haik
Jun 8, 2016 at 15:20
• @haik to compute that, just invert their bound. Jun 8, 2016 at 15:22
• Thanks again. And I'll think it over, since my major is not math.
– haik
Jun 8, 2016 at 15:29