Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleComparison between XL and Gr\"obner basis algorithms.
Author(s) Gwenole Ars, Hideki Imai, Faug`ere Jean-Charles, Mitsuru Kawazoe, Makoto Sugita
TypeBook, Chapter in Book, Conference Proceeding
AbstractThis 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 semi-regular 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.
KeywordsMultivariate polynomial equations, Algebraic attacks, Solving Systems
URL http://link.springer.com/chapter/10.1007%2F978-3-540-30539-2_24
PublisherBerlin: Springer
Translation No
Refereed No