HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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$.
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070747
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 9:29:59 PM
Last modification on : Tuesday, January 12, 2021 - 9:36:03 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:50:15 PM

Identifiers

  • HAL Id : inria-00070747, version 1

Citation

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⟩

Share

Metrics

Record views

166

Files downloads

509