Asymptotic Behaviour of the Index of Regularity of Semi-Regular Quadratic Polynomial Systems

Magali Bardet (1) , Jean-Charles Faugère (1) , Bruno Salvy

1 SPIRAL - Systèmes Polynomiaux, Implantation, Résolution Algébrique

We compute the asymptotic expansion of the index of regularity for overdetermined quadratic semi-regular sequences of algebraic equations. This implies bounds for the generic complexity of Gr ̈obner bases algorithms, in particular the F 5 [Fau02] algorithm. Bounds can also be derived for the XL [SPCK00] family of algorithms used by the cryptographic community.

Domaines: Informatique [cs]

Magali Bardet, Jean-Charles Faugère, Bruno Salvy. Asymptotic Behaviour of the Index of Regularity of Semi-Regular Quadratic Polynomial Systems. MEGA 2005 - 8th International Symposium on Effective Methods in Algebraic Geometry, May 2005, Porto Conte, Alghero, Sardinia, Italy. pp.1-17. ⟨hal-01486845⟩