Comparison Between XL and Grobner Basis Algorithms

摘要

This paper compares the XL algorithm with known Grobner basis algorithms. We show that to solve a system of algebraic equations via the XL algorithm is equivalent to calculate the reduced Grobner basis of the ideal associated with the system. Moreover we show that the XL algorithm is also a Groebner basis algorithm which can be represented as a redundant variant of a Grobner basis algorithm F_4. Then we compare these algorithms on semi-regular sequences, which correspond, in conjecture, to almost all polynomial systems in two cases: over the fields F_2 and F_q with q n. We show that the size of the matrix constructed by XL is large compared to the ones of the F_5 algorithm. Finally, we give an experimental study between XL and the Buchberger algorithm on the cryptosystem HFE and find that the Buchberger algorithm has a better behavior.