Comparison of XL and Gröbner basis algorithms over Finite Fields - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Research Report) Year : 2004

Comparison of XL and Gröbner basis algorithms over Finite Fields

Abstract

This paper compares the XL algorithm with Gröbner basis algorithm. We explain the link between XL computation result and Gröbner basis with the well-known notion of $D$-Gröbner basis. Then we compare these algorithms in two cases: in the fields $\Fand $\Fwith $q\gg n$. For the field $\F we have proved that if XL needs to compute polynomial with degree $D$ to terminate, the whole Gröbner basis is computated without exceeding the degree $D$. We have studied the XL algorithm and $F_5$ algorithm on semi-regular sequences introduced in report~\cite{F5_complexite}. We show that the size of matrix constructed by XL is huge compared to the ones of $F_5$. So the complexity of XL is worth than $F_5$ algorithm on these systems. For the field $\F we introduce an emulated algorithm using Gröbner basis computation to have a comparison between XL and Gröbner basis. We have proved that this algorithm will always reach a lower degree for intermediate polynomials than XL algorithm. A study on semi-regular sequences shows that $F_5$ always has a better behavior than XL algorithm especially when $m$ is near from $n$.
Fichier principal
Vignette du fichier
RR-5251.pdf (433.67 Ko) Télécharger le fichier
Loading...

Dates and versions

inria-00070747 , version 1 (19-05-2006)

Identifiers

  • HAL Id : inria-00070747 , version 1

Cite

Jean-Charles Faugère, Gwénolé Ars. Comparison of XL and Gröbner basis algorithms over Finite Fields. [Research Report] RR-5251, INRIA. 2004, pp.26. ⟨inria-00070747⟩
202 View
652 Download

Share

Gmail Facebook X LinkedIn More