Description
Date depot: 1 janvier 1900
Titre: Résolution des systèmes polynomiaux multi-homogènes et Applications à la cryptanalyse algébrique et à la géométrie réelle
Directeur de thèse:
Mohab SAFEY EL DIN (LIP6)
Directeur de thèse:
Jean-Charles FAUGÈRE (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
La résolution des systèmes polynomiaux est un problème central en Calcul Formel du fait
de ses nombreuses applications. Les méthodes de résolution algébriques ont déjà montré leur
intérêt dans au moins les deux domaines importants que sont la cryptanalyse algébrique et la
géométrie réelle et qui constituent les champs d’applications de cette thèse.
Les bases de Gröbner [1] constituent une brique essentielle pour la résolution [2]. Les
nouvelles générations d’algorithmes pour le calcul de bases de Gröbner (en particulier les
algorithmes F4 et F5 [4, 5]) permettent aujourd’hui la résolution d’applications hors d’atteinte
par d’autres méthodes. Ces algorithmes réduisent le problème de calcul de bases de Gröbner
à des problèmes d’algèbre linéaire (les polynômes sont codés comme des vecteurs de
monômes). L’algorithme F5 a la particularité d’éviter de nombreux calculs intermédiaires «inutiles
» : en effet, des premières analyses ont montré que les matrices construites sont de taille
optimale dans le cas fréquent des systèmes réguliers [5].
Les systèmes polynomiaux issus des applications ne sont en général pas aléatoires mais
possèdent souvent une structure (symétries, polynômes creux,. . .) ; en particulier un grand
nombre d’entre eux ont une structure multi-homogène. Dans le cadre de cette thèse les deux
applications visés sont d’une part la cryptanalyse algébrique et d’autre part les problèmes
d’optimisation et les liens avec la géométrie réelle. À l’instar des résultats obtenus dans [10]
analysant l’algorithme F5 dans le cas des systèmes sur-déterminés semi-réguliers, il est naturel
d’étudier et de chercher à améliorer cet algorithme dans le but d’exploiter la structure
multi-homogène de ces systèmes.
La version classique de l’algorithme F5 ne permet pas d’éliminer tous les calculs inutiles
dans le cas des systèmes multi-homogènes (les matrices construites ne sont pas de rang
maximal si bien que des réductions à zéro sont calculées). De plus et dans un autre contexte,
il a été montré [3] que dans le cas de certains systèmes polynomiaux multi-homogènes, le
résultant de Macaulay pouvait être calculé en faisant intervenir des matrices de taille significativement
plus petite que celle de la matrice de Macaulay générique. Ce résultant est calculé à
partir de la matrice de Macaulay qui est corrélée à celles apparaissant dans F5. Notons enfin
que dans le cas des systèmes multi-homogènes, le nombre de solutions donné par la borne de Bézout multi-homogène [16] est significativement inférieur aux bornes qui sont atteintes
dans les situations génériques.
Un premier objectif de la thèse est donc de concevoir une version «optimisée» de l’algorithme
F5 pour le cas des systèmes multi-homogènes assurant que (sous certaines conditions
de régularité), tous les calculs inutiles soient éliminés. Un premier pas important dans cette
direction a été accompli par P.-J. Spaenlehauer : dans le cas restreint, mais important, des
systèmes bi-linéaires (c’est à dire homogènes de degré 2 et linéaires par rapport à deux ensembles
de variables), une nouveau critère à la F5 a été proposé qui permet d’éviter tous les
calculs intitules pour les systèmes bi-linéaires bi-réguliers. L’extension de cette version de F5
aux cas multi-linéaires puis multi-homogènes reste à faire et constitue donc l’objectif principal
de la thèse. Il s’agira aussi de valider expérimentalement ces avancées algorithmiques par des
implantations.
Un deuxième objectif est d’étudier la structure des matrices apparaissant dans ces nouvelles
versions de F5. L’exploitation de la structure multi-homogène pourrait conduire à considérer
des matrices de taille significativement plus petite, comme c’est le cas pour le calcul du
résultant de Macaulay.
Un troisième objectif est l’analyse fine de la complexité de ces versions modifiées de l’algorithme
F5. Il faut pour cela borner la taille de la plus grosse matrice apparaissant en cours
de calculs. Un outil mathématique essentiel pour effectuer cette analyse est la (multi)-série de
Hilbert. La connaissance de la structure de cette série est un préalable à l’analyse fine de la
complexité des versions multi-homogènes de F5.
Doctorant.e: Spaenlehauer Pierre-Jean