Solving polynomial systems over finite fields : Algorithms, Implementations and applications
Chenqi Mou · 2013
Resolution de systemes polynomiaux sur les corps finis est d’un interet particulier en raison de ses applications en Cryptographie, Theorie du Codage, et d’autres domaines de la science de l’information. Dans cette these, nous etudions plusieurs aspects importants theoriques et informatiques pour resolution de systemes polynomiaux sur les corps finis, en particulier sur les deux outils largement utiliss: bases de Grobner et ensembles triangulaires. Nous proposons des algorithmes efficaces pour le changement de l’ordre des bases de Grobner d’ideaux de dimension zero en utilisant le faible densite des matrices de multiplication et d’evaluer telle faible densite pour les systemes de polynomes generiques. Algorithmes originaux sont presentes pour la decomposition des ensembles de polynomes en ensembles triangulaires simples sur les corps finis. Nous definissons egalement decomposition sans carre et factorisation des polynomes sur produits non melanges d’extensions des corps et proposons des lgorithmes pour les calculer. L’efficacite et l’efficience de ces algorithmes ont ete verifiees par des experiences avec nos implementations. Methodes de resolution de systemes polynomiaux sur les corps finis sont egalement appliquees pour resoudre les problemes pratiques poses par la Biologie et la Theorie du Codage.