Résumé de thèse
Magali Bardet
Soutenue le 08 Décembre 2004
Les bases de Gröbner constituent un outil important pour la résolution
de systèmes d'équations algébriques, et leur calcul est souvent la
partie difficile de la résolution. Cette thèse est consacrée à des
analyses de complexité de calculs de bases de Gröbner pour des
systèmes surdéterminés (le nombre m d'équations est supérieur au
nombre n d'inconnues).
Dans le cas générique ("aléatoire"), des outils existent pour analyser
précisément la complexité du calcul de base de Gröbner d'un système
non surdéterminé (suites régulières, borne de Macaulay). Nous avons
étendu ces résultats au cas surdéterminé, en définissant les suites
semi-régulières et le degré de régularité dont nous donnons une
analyse asymptotique précise. Par exemple dès que m>n nous gagnons
un facteur 2 sur la borne de Macaulay, et un facteur 11,65 quand
m=2n (ces facteurs se répercutent sur l'exposant de la
complexité globale). Nous déterminons la complexité de l'algorithme F5
(Faugère) de calcul de base de Gröbner.
Ces résultats sont appliqués en protection de l'information, où les
systèmes sont alors considérés modulo 2 : analyse de la complexité des
attaques algébriques sur des cryptosystèmes, algorithmes de décodage
des codes cycliques. Dans ce dernier cas, une remise en équation
complète du problème conduit à utiliser des systèmes de dimension
positive dont la résolution est de manière surprenante plus
rapide. Nous obtenons ainsi un algorithme de décodage efficace de
codes précedemment indécodables, permettant un décodage en liste et
applicable à tout code cyclique.
Abstract
Gröbner bases constitute an important tool for solving algebraic
systems of equations, and their computation is often the hard part of
the resolution. This thesis is devoted to the complexity analysis of
Gröbner basis computations for overdetermined algebraic systems (the
number m of equations is greater than the number n of variables).
In the generic (”random”) case, tools exist to analyze the
complexity of Gröbner basis computations for a non overdetermined
system (regular sequences, Macaulay bound). We extend these results to
the overdetermined case, by defining the semiregular sequences and the
degree of regularity for which we give a precise asymptotic
analysis. For example as soon as m > n we gain a factor 2 on
the Macaulay bound, and a factor 11,65 when m = 2n (these
factors are reflected on the exponent of global complexity). We
determine the complexity of the F5 Algorithm (J-C. Faugère) for
computing Gröbner bases.
These results are applied in information theory, where the
systems are then considered modulo 2 : analysis of the complexity of
the algebraic attacks on cryptosystems, algorithms for the decoding of
cyclic codes. In this last case, a new equation set-up of this problem
leads to use systems of positive dimension for which the resolution is
in a surprising way faster. We thus obtain an effective algorithm for
decoding codes previously undecodable, allowing list decoding and
applicable to any cyclic code.
dernière modification : December 15, 2004.