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.
Category / Keywords: multivariate cryptography, cryptography,polynomial equations over finite field, algebraic attack, Dixon Resultants, DR. Date: received 5 Sep 2005 Contact author: tangxij at mails gucas ac cn Available format(s): PDF | BibTeX Citation Version: 20050912:120940 (All versions of this report) Short URL: ia.cr/2005/312