Welcome to the resource topic for
**2005/312**

**Title:**

A New Efficient Algorithm for Solving Systems of Multivariate Polynomial Equations

**Authors:**
Xijin Tang, Yong Feng

**Abstract:**

The security of many recently proposed cryptosystems is based on the

difficulty of solving large systems of quadratic multivariate

polynomial equations. The classical algorithm for solving such a

system is Buchberger’s algorithm for constructing Gröbner bases.

Another algorithm for solving such a system is XL algorithm. For

sparse system, Buchberger’s algorithm benefits from sparsity of the

system, but its complexity is impractical and hard to determine.

XL could not make a good use of sparse structure of the system,

since XL has no good strategy of choosing the multiply monomials.

In this paper, based on Extended Dixon Resultants, a new algorithm

DR is proposed to solve systems of multivariate polynomial

equations. The basic idea of DR is to apply Extended Dixon

Resultants method to system of multivariate polynomial equations, by

taking x_1 \ldots x_{n-1} as variables and x_n as parameter.

The time complexity of DR technique is evaluated, it seems to be

polynomial when the system is sparse and m=n and mixed volume is

polynomial. As far as we know, it is the first algorithm which has

better behavior than exhaustive search for some sparse systems over

large field. Moreover, DR technique is compared with Buchberger’s

algorithm and XL technique in this paper. It is shown that DR is far

more efficient than Buchberger’s algorithm and XL when m=n. DR is

a quite efficient algorithm, it makes a good use of the sparsity of

the sparse system. Besides its efficiency, another advantage of DR

is that its complexity is easy to determine.

**ePrint:**
https://eprint.iacr.org/2005/312

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .