Le jeudi 10 décembre à 10h en salle 201, Charles Bouillaguet, Maître de Conférences à l'Université de Lille 1 et membre du laboratoire Cristal viendra faire un séminaire au sein du laboratoire.
Dans le fond, un système d’équations polynomiales modulo 2 est un système d’équations entre des variables booléennes. La multiplication correspond en effet au ET logique, et l’addition au XOR. Ceci ressemble fortement au problème SAT, et d’ailleurs la résolution de tels système est également un problème NP-complet. Les deux problèmes sont cependant assez différents. Dans le cas des systèmes polynomiaux, il n’existe rien de comparable à l’algorithme DPLL qui a tant de succès pour résoudre des instances de SAT. D’ailleurs, on ne dispose pas aujourd’hui d’algorithme efficace permettant de résoudre des systèmes polynomiaux aléatoires (ceci a motivé leur usage dans un contexte cryptographique).
Dans cet exposé, je présenterai les principales techniques de résolution de systèmes polynomiaux (méthodes algébriques, réduction à SAT, recherche exhaustive). Je présenterai l’algorithme (relativement simple) que j’ai conçu, ainsi que les ruses qui ont permis de l’implémenter efficacement.
