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?


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.


1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .