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.