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

Details:

   
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
ISBN3-540-23975-8/pbk
URL http://link.springer.com/chapter/10.1007%2F978-3-540-30539-2_24
LanguageEnglish
Pages338--353
PublisherBerlin: Springer
Year2004
Edition0
Translation No
Refereed No
Webmaster