Retour au reportage Retour au reportage
20210159_0067

© Christian MOREL / IRIF / CNRS Images

Référence

20210159_0067

Test d’identité pour les formules algébriques

Test d’identité pour les formules algébriques. En considérant un circuit arithmétique qui calcule une formule mathématique, un problème décisionnel fondamental consiste à vérifier si la formule s’évalue partout à zéro. L'un des problèmes qui se pose lorsqu'il s'agit de décider de la propriété d’être nul est que de telles formules peuvent impliquer des coefficients très importants. Ces formules sont donc coûteuses à représenter explicitement dans les ordinateurs, et donc difficiles à calculer de manière efficace. Une technique pour surmonter ce problème consiste à examiner leur réduction modulo de quelques nombres premiers (idéaux) et à les évaluer dans un champ fini. Les formules du tableau fournissent le contexte mathématique nécessaire pour choisir le bon nombre premier (idéal) et construit une telle représentation réduite d'une manière qui garantit que le calcul est correct lors de l'évaluation de circuits arithmétiques sur des nombres algébriques.

Délégation(s)

Thématiques scientifiques

CNRS Images,

Nous mettons en images les recherches scientifiques pour contribuer à une meilleure compréhension du monde, éveiller la curiosité et susciter l'émerveillement de tous.