Séminaire du 25 novembre 02, Magali Bardet, Projet SPACES LIP6/LORIA

Complexité des systèmes aléatoire dans un corps fini

Nous établissons des bornes de complexité théorique très précises pour les systèmes algébriques aléatoires dans un corps fini, en tenant compte des degrés $d_i$ de chacune des équations. En particulier nous déterminons un analogue de la borne de Macaulay $1 + \sum_i (d_i -1)$ (Lazard 83). Ces bornes sont valides y compris lorsque le nombre d'équations $m$ est plus grand que le nombre de variables $n$. Le calcul d'un développement asymptotique se fait en calculant les séries génératrices associées puis en utilisant la méthode des points cols coalescents. Par exemple dans le cas $m=2 n$ et $d_i=d$, la borne de Macaulay devient $A(d)n + B(d)n^{\frac{1}{3}} + o(1)$ où $A(d)$ est un nombre algébrique et $B(d)$ s'exprime en fonction du plus grand zéro de la fonction Ai d'Airy. Les deux premiers termes de ce développement asymptotique donnent une approximation quasi exacte de la borne de Macaulay dès que $n\geq 3$.

Ces bornes théoriques sont particulièrement utiles pour faire la distinction en pratique entre un système aléatoire (difficile) et un système provenant de HFE (plus facile). Travail en collaboration avec B. Salvy et J.-C. Faugère.