Fonction booléenne

vignette|Arbre de décision binaire Une fonction booléenne est une fonction prenant en entrée une liste de bits et donnant en sortie un unique bit. Les fonctions booléennes sont très utilisées en informatique théorique, notamment en théorie de la complexité et en cryptologie (par exemple dans les boîtes-S et les chiffrements par flot -- fonction de filtrage ou de combinaison de registres à décalage à rétroaction linéaire). Une fonction booléenne est une fonction de dans où désigne le corps fini à 2 éléments. Un exemple de fonction booléenne est la fonction parité, dont la sortie dépend de la parité du nombre de 1 dans l'entrée. Une fonction booléenne peut être représentée par un circuit booléen. Les corps finis et les polynômes interpolateurs de Lagrange conduisent rapidement à une propriété fondamentale des fonctions booléennes : la représentation dite « forme algébrique normale » (algebraic normal form ou ANF). Toute fonction booléenne peut s'écrire comme un polynôme en variables à coefficients dans . Cependant, différents polynômes de donnent la même fonction. Par exemple, et donnent bien la même valeur lorsqu'ils sont évalués sur un élément de . Pour obtenir une représentation unique, il faut considérer les éléments de l'anneau quotient, soit : Autrement dit, une fonction booléenne peut être représentée de manière unique par un polynôme de la forme : ( est une suite d'éléments de et ). On pose fréquemment , et , permettant l'écriture compacte : La notion de degré d'une fonction booléenne est alors évidente, il s'agit du degré maximal des monômes de son ANF. Exemple de forme algébrique normale sur : Les fonctions de degré 1 sont appelées les fonctions affines. En fait, ce sont des formes affines de l'espace vectoriel — vu comme espace sur le corps . Ce sont les fonctions les plus simples, hormis les constantes. Il a fini par apparaître que « ressembler » à une fonction linéaire était une propriété pouvant être exploitée en cryptanalyse.