Details:
Title  Comparison between XL and Gr\"obner basis algorithms.  Author(s)  Gwenole Ars, Hideki Imai, Faug`ere JeanCharles, Mitsuru Kawazoe, Makoto Sugita  Type  Book, Chapter in Book, Conference Proceeding  Abstract  This paper compares the XL algorithm with known Gröbner basis algorithms. We show that to solve a system of algebraic equations via the XL algorithm is equivalent to calculate the reduced Gröbner basis of the ideal associated with the system. Moreover we show that the XL algorithm is also a Gröbner basis algorithm which can be represented as a redundant variant of a Gröbner basis algorithm F 4. Then we compare these algorithms on semiregular sequences, which correspond, in conjecture, to almost all polynomial systems in two cases: over the fields 𝔽2 and 𝔽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.  Keywords  Multivariate polynomial equations, Algebraic attacks, Solving Systems  ISBN  3540239758/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F9783540305392_24 
Language  English  Pages  338353  Publisher  Berlin: Springer  Year  2004  Edition  0  Translation 
No  Refereed 
No 
