Complexity of Gröbner basis computation for Semi-regular Overdetermined sequences over F_2 with solutions in F_2

Magali Bardet 1, 2 Jean-Charles Faugère 1, 2 Bruno Salvy 3
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : We present complexity results for solving "typical"overdetermined algebraic systems over GF(2) with solutions in GF(2) using Gröbner bases. They are useful for instance to predictthe complexity of an algebraic cryptanalysis over a cryptosystem,they give a priori upper bounds. We define semi-regularsequences and their associated notion of degree of regularity Dreg.The motivation for studying semi-regular sequences is that"random" sequences are semi-regular, and Dreg is closely related tothe global cost of the Gröbner basis computation for a gradedadmissible monomial order. Using inparticular the F5 Gröbner basis algorithm, we show that forsemi-regular sequences the behavior of F5 (in a matrix version)can be followed step by step, and the size of all matrices madeexplicit. We deduce Dmax, and using asymptotic analysis methodswe compute its asymptotic expansion. We give many explicitexamples, and discuss the complexity of the global arithmeticcost of the Gröbner basis computation for m quadratic equations in n variables: for m=N n with N constant, the computationis exponential, if n
Type de document :
Rapport
[Research Report] RR-5049, INRIA. 2003
Liste complète des métadonnées

https://hal.inria.fr/inria-00071534
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 23 mai 2006 - 17:52:56
Dernière modification le : mardi 25 octobre 2016 - 16:57:20
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:23:19

Fichiers

Identifiants

  • HAL Id : inria-00071534, version 1

Collections

Citation

Magali Bardet, Jean-Charles Faugère, Bruno Salvy. Complexity of Gröbner basis computation for Semi-regular Overdetermined sequences over F_2 with solutions in F_2. [Research Report] RR-5049, INRIA. 2003. <inria-00071534>

Partager

Métriques

Consultations de
la notice

410

Téléchargements du document

834