Paper 2004/112

Relation between XL algorithm and Groebner Bases Algorithms

M. Sugita and M. Kawazoe and H. Imai

Abstract

We clarify a relation between the XL algorithm and Groebner bases algorithms. The XL algorithm was proposed to be a more efficient algorithm to solve a system of equations with a special assumption without trying to calculate a whole Groebner basis. But in our result, it is shown that the XL algorithm is also a Groebner bases algorithm which can be represented as a redundant version of a Groebner bases algorithm F4 under the assumption in XL.

Note: Appendix is added.