Calcul efficace des bases de Gröbner et applications

Le sujet de cette thèse est la résolution efficace des systèmes d'équations polynomiales par des méthodes exactes du Calcul Formel. De même que pour l'étude des systèmes linéaires l'objet mathématique fondamental est la notion d'espace vectoriel, pour les systèmes algébriques l'objet fondamental est l'idéal associé aux équations. Algorithmiquement le seul objet connu pour représenter un idéal est la notion de base de Gröbner introduite par B. Buchberger. L'algorithme historique de calcul des bases de Gröbner est l'algorithme de Buchberger qui se révèle, en pratique, très insuffisant pour traiter des applications conséquentes. Les résultats suivants permettent de lever trois obstructions fondamentales: * Le concept de changement d'ordre: l'idée est de calculer d'abord une base pour un ordre "facile" puis de changer efficacement d'ordre en tirant partie du fait qu'on a déjà une base de Gröbner. J'ai proposé deux algorithmes pour cette opération: l'algorithme FGLM et une version polynomiale de l'algorithme LLL. FGLM est implanté dans tous les systèmes de Calcul Formel. * L'algorithme F4 permet d'éviter les choix arbitraires de paires critiques et ramène le problème de calculer une base de Gröbner à la mise sous forme échelon d'une matrice. C'est maintenant l'algorithme par défaut de certains logiciels. * L'algorithme F5 permet sous certaines hypothèses de régularité du système initial d'éviter tous les calculs inutiles; autrement dit l’algorithme ne génère que des matrices dont le rang est plein (donc de tailles optimales). Ces algorithmes ont été implantés en langage de bas niveau (environ 242000 lignes de C et assembleur) dans le logiciel FGb; dans le cadre d'un contrat avec la société MapleSoft , ce logiciel ainsi que des logiciels complémentaires du projet SALSA, sont accessibles depuis le système généraliste de Calcul Formel Maple. Ces logiciels et algorithmes ont été mis à contribution pour traiter plusieurs applications (souvent en collaboration avec des spécialistes du domaine applicatif) : 1) Cas continu : les applications de type ingénierie dans lesquels on cherche les solutions réelles d'un système polynomial. Dans ce cas, le calcul de base de Gröbner peut être assimilé à une phase de précalcul symbolique; la deuxième phase du calcul nécessitant de calculer d'autres objets mathématiques (isolation de racines réelles, RUR, variété discriminante). Parmi les applications qui ont été abordées avec succès on peu citer notamment: Théorie du Signal, Robotique, Géométrie Algorithmique, Biologie. 2) Cas discret : dans ce cas on cherche les solutions dans un corps finis. Outre le décodage des codes cycliques on peut mentionner un vaste champ d'applications de ces techniques dans le domaine de la Cryptologie: la cryptanalyse algébrique qui consiste à modéliser un cryptosystème de manière algébrique puis d’en évaluer la robustesse en mesurant la difficulté de résolution des équations correspondantes. Ce sujet est maintenant un domaine très actif en Cryptologie et a permis de démontrer la faiblesse de plusieurs cryptosystèmes. Ainsi pour le cryptosystème HFE de Patarin, une version modifiée de l'algorithme F5 a permis de « casser » un exemple réaliste de HFE sur 80 bits (alors que les meilleures implantations de l'algorithme de Buchberger était limitée à 25/30 bits). La plupart des problèmes issus des applications ont la particularité de se modéliser par des systèmes polynomiaux pour lesquels le nombre d'équations est bien supérieur aux nombres de variables. Dans ce cas, une analyse de complexité de l'algorithme F5 a permis de quantifier le gain obtenu pour le calcul: plus il y a d'équations par rapport aux nombre de variables plus le calcul de la base de Gröbner est rapide (on peut même montrer que le temps de calcul est sous-exponentiel ou polynomial lorsque le rapport nombre de variables sur nombre d'équations diminue). Ce résultat est maintenant utilisé pour concevoir des cryptosystèmes robuste vis à vis des attaques algébriques (par exemple QUAD).

28 Doctores 2003 - 2021