Un problème important en cryptographie, mais aussi en informatique théorique, est celui de l’existence de solutions F2-rationnelles d’un système polynomial multivarié sur F2, problème dont on sait qu’il est NP-complet. Cela revient à travailler dans des anneaux booléens, i.e. dans lesquels f^2=f pour tout polynôme f. L’approche algébrique de ce problème consiste à calculer une base de Gröbner de l’idéal associé au système. Il est alors important d’estimer les tailles des matrices de Macaulay intervenant dans ce calcul, ce qui correspond à l’étude de la série de Hilbert d’un idéal booléen. On verra comment l’utilisation de certains outils d’algèbre homologique, adaptés au cas booléen, permet alors d’éclairer la complexité de la résolution de ces systèmes.
