Fonction booléenne 435884 31702891 2008-07-19T11:51:22Z Sherbrooke 18624 Raccourcir. Une '''fonction booléenne''' est une fonction de <math>\mathbb{F}^n</math> dans <math>\mathbb{F}</math> où <math>\mathbb{F}</math> désigne le [[corps fini]] à 2 éléments. En fait, les fonctions booléennes sont simplement un autre nom des [[fonction logique|fonctions logiques]]. Toutefois, lorsque l'on s'attache aux propriétés algébriques de ces fonctions, l'appellation ''fonction booléenne'' est la plus utilisée. Les fonctions booléennes, ou plus précisément leurs propriétés, interviennent notamment en [[cryptologie]] dans les [[S-Box|boîtes-S]], ainsi que dans les [[chiffrement par flot|chiffrements par flot]] -- fonction de filtrage ou de combinaison des [[registre à décalage|registres à décalage]]. ==Propriétés== ===Forme algébrique normale=== Les [[corps (mathématiques)|corps]] finis et les [[polynôme|polynômes]] interpolateurs de [[Joseph-Louis Lagrange|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 <math>n</math> variables à coefficients dans <math>\mathbb{F}</math>. Cependant, différents polynômes de <math>\mathbb{F}[X_0,...,X_{n-1}]</math> donnent la même fonction. Par exemple, <math>X_0^2</math> et <math>X_0^3</math> donnent bien la même valeur lorsqu'ils sont évalués sur un élément de <math>\mathbb{F}^n</math>. Pour obtenir une représentation unique, il faut considérer les éléments de l'[[anneau (mathématiques)|anneau]] quotient, soit : : <math>\mathbb{F}[X_0,...,X_{n-1}]/(X_0^2+X_0,...,X_{n-1}^2+X_{n-1})</math> Autrement dit, une fonction booléenne peut être représentée de manière unique par un polynôme de la forme : : <math>P(X_0,...,X_{n-1}) = \sum_{(u_0,...,u_{n-1})\in\mathbb{F}^n} a_u\prod_{i=0}^{n-1}X_i^{u_i}</math> On pose fréquemment <math>u=(u_0,...,u_{n-1})~</math>, <math>X=(X_0,...,X_{n-1})~</math> et <math>X^u=\prod_{i=0}^{n-1}X_i^{u_i}</math>, permettant l'écriture compacte : : <math>P(X)=\sum_{u\in\mathbb{F}^n} a_uX^u</math>. La notion de degré d'une fonction booléenne est alors évidente, il s'agit du degré maximal des monômes de son ANF. ===Linéarité et Non-linéarité=== Les fonctions de degré 1 sont appelées les fonctions ''affines''. En fait, ce sont des formes affines de l'espace vectoriel <math>\mathbb{F}^n</math> -- vu comme espace sur le corps <math>\mathbb{F}</math>. 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]]. La ressemblance en question se base sur le nombre de fois où deux fonctions prennent la même valeur, il s'agit de la [[distance de Hamming]] : :<math>d_H(f,g) = \#\{u\in\mathbb{F}^n : f(u)\neq g(u)\}</math> Les cryptographes utilisent le terme de ''non-linéarité'' pour parler de la distance d'une fonction booléenne à l'ensemble <math>\mathcal{A}</math> des fonctions affines : :<math>\mathcal{N}(f)=\min \{d_H(f,g) : g\in \mathcal{A}\}</math> L'intérêt de cette notion est de quantifier l'erreur commise si on remplace la fonction <math>f</math> par une fonction affine : dans le meilleur des cas, on se « trompe » <math>\mathcal{N}(f)</math> fois sur <math>2^n</math> si <math>n</math> est le nombre de variables. On montre, en utilisant la transformée de Fourier, que la non-linéarité d'une fonction booléenne est au plus de :<math>\mathcal{N}(f)\le 2^{n-1}-2^{\frac{n}{2}-1}</math> Lorsque <math>n</math> est pair, cette borne supérieure est atteinte, on parle alors de [[fonction courbe]]. Précisons que l'ensemble des fonctions affines a une importance particulière en théorie des [[code correcteur|codes correcteurs]], au point qu'il possède un nom, le [[code de Reed-Muller]] d'ordre <math>1</math> (en <math>n</math> variables). L'ordre est le degré maximal des fonctions. Ainsi, le code de Reed-Muller d'ordre <math>r~</math> en <math>n~</math>, usuellement noté <math>\mathrm{RM}(r,n)~</math> est l'ensemble des fonctions en <math>n~</math> variables de degré au plus <math>r~</math>. Dans le contexte de la théorie des codes, la non-linéarité maximale se trouve correspondre au « rayon de recouvrement » du code <math>\mathrm{RM}(1,n)~</math>, c'est-à-dire, la distance maximale entre un mot binaire de longueur <math>2^n</math> et un mot du code. ==Outil d'étude : la [[transformée de Fourier]]== La [[Transformée de Fourier|transformation de Fourier]], appliquée aux fonctions booléennes, se révèle être un moyen très puissant pour explorer les différentes propriétés de ces objets. Elle est, par exemple, fréquemment utilisée pour étudier des propriétés [[cryptographie|cryptographique]]s comme la [[fonction courbe|non-linéarité maximale]]. On la retrouve également dans des aspects plus appliquées : l'existence d'algorithmes de calcul de la transformée de Fourier de type [[Transformée de Fourier rapide|FFT]] sert à décoder efficacement les [[code de Reed-Muller|codes de Reed et Muller]]. On trouvera dans la suite une présentation générale de la transformation de Fourier dans le cas des groupes abéliens finis qui est ensuite particularisée pour le cas des fonctions booléennes. === Cas d'un groupe abélien fini === {{Article détaillé|Théorème de Kronecker}} Dans le cas d'un groupe abélien fini, le théorème de Kronecker assure que le groupe est isomorphe à un [[produit direct (groupes)|produit direct]] de [[groupe cyclique|groupes cycliques]]. Ce théorème est à la base de nombreuses propriétés des fonctions booléennes. ==== Caractère et groupe dual ==== {{Article détaillé|Caractère d'un groupe fini}} De manière générale, on peut définir une transformation de Fourier sur un [[Groupe (mathématiques)|groupe]] <math>\mathcal G</math> en utilisant la notion de caractère. Un ''caractère'' <math>\chi</math> est un [[morphisme]] de <math>\mathcal G</math> dans <math>\mathbb U</math>, le groupe des [[Racine de l'unité|racines de l'unité]] du corps des [[nombres complexes]] <math>\mathbb C</math>. L'ensemble des caractères opèrent sur l'ensemble des applications de <math>\mathcal G</math> dans <math>\mathbb C</math>, cet ensemble est appelé [[algèbre d'un groupe fini|algèbre du groupe]] et est généralement noté <math>\mathbb C[\mathcal G]</math>. Il est munis du [[produit hermitien]] suivant : :<math>\forall \chi_1, \chi_2 \in \mathbb C[\mathcal G] \quad <\chi_1 |\chi_2> = \frac 1{|\mathcal G|}\sum_{g \in \mathcal G} \chi_1(g)^*.\chi_2(g)</math> Ici si ''z'' est un complexe, ''z''<sup>*</sup> désigne son [[conjugué]]. Les caractères forment une [[base orthonormale]] de l'algèbre du groupe. L'ensemble des caractères de <math>\mathcal G</math> peut être muni d'une structure de groupe en utilisant la multiplication entre applications, ce groupe est appelé le groupe dual. le groupe <math>\mathcal G</math> et son dual son isomorphes si <math>\mathcal G</math> est [[groupe abélien|abélien]]. ''Les démonstrations sont données dans l'article détaillé.'' ==== Définition de la transformée de Fourier ==== {{Article détaillé|Analyse harmonique sur un groupe abélien fini}} Lorsque <math>\mathcal G</math> est [[Groupe abélien|abélien]] et fini, il est possible de définir simplement la [[transformée de Fourier]]. On appelle ''transformée de Fourier'' d'un élément de l'algèbre du groupe de <math>{\mathcal G}</math> une application du groupe dual <math>\mathcal F (\mathcal G)</math> dans <math>\mathbb C</math> notée ici <math>{\mathcal F}(f)</math> et définie par : : <math>\forall \chi \in \mathcal F (\mathcal G) \quad {\mathcal F}(f)(\chi)=\frac 1{\sqrt {|\mathcal G |}}\sum_{x\in{\mathcal G}}f(x)\chi(x)^*</math> Cette application dispose de toutes les propriétés usuelles d'une transformée de Fourier, elle est linéaire, l'[[égalité de Parseval]] le [[théorème de Plancherel]], la [[formule sommatoire de Poisson]] et la [[dualité de Pontryagin]] sont par exemple vérifiées. Il est aussi possible de définir un [[produit de convolution]]. ''Les démonstrations sont données dans l'article détaillé.'' ==== Espace vectoriel fini ==== {{Article détaillé|Analyse harmonique sur un espace vectoriel fini}} Il existe un cas important, celui où le groupe est un espace vectoriel fini ''V'', donc de dimension fini sur un [[corps fini]] <math>\mathbb K</math>. Dans ce cas, il existe un isomorphisme entre ''V'' et son groupe dual, appelé [[dualité de Pontryagin]]. Soit '''.''' une [[forme bilinéaire]] non dégénérée de ''V'' et μ un caractère non trivial de <math>\mathbb K</math>, l'application χ de ''V'' dans son dual, qui à ''y'' associe le caractère χ<sub>y</sub> définie par l'égalité suivante est cet isomorphisme : : <math>\forall x \in V \quad \chi_y(x) = \mu (y.x)</math> Cet isomorphisme permet d'exprimer la transformation de Fourier d'un élément ''f'' de l'algèbre du groupe de ''V'' de la manière suivante : : <math>\forall \zeta \in V \quad {\mathcal F}(f)(\zeta)=\frac 1{\sqrt {|V|}}\sum_{x\in V}f(x)\mu(-\zeta.x)</math> ===Espace vectoriel sur le corps ''F''<sub>2</sub>=== ==== Formes des caractères et isomorphisme avec le dual==== On considère maintenant le cas où le corps <math>\mathbb K</math> est celui à deux éléments noté <math>\mathbb F_2</math> et l'espace vectoriel est <math>\mathbb F_2^n</math> où ''n'' est un entier strictement positif. Soit ''x'' = (''x''<sub>i</sub>) et ''y'' = (''y''<sub>i</sub>) deux éléments de l'espace vectoriel, la forme bilinéaire '''.''' est définie par : :<math> x.y = \sum_{i=1}^n x_i.y_i</math> Il n'existe que deux caractères dans <math>\mathbb F_2</math>, le caractère trivial et celui qui à ''s'' associe (-1)<sup>s</sup>. Comme il n'existe qu'un caractère non trivial, l'isomorphisme χ du paragraphe précédent prend la forme suivante : :<math>\forall x,y \in \mathbb F_2^n \quad \chi_y(x) = (-1)^{x.y}</math> ====Transformation de Walsh==== {{Article détaillé|Transformée de Walsh}} Dans le cas d'un espace vectoriel binaire (ie. sur le corps fini à deux éléments) la transformée de Fourier prend le nom de '''transformée de Walsh'''. Elle prend la forme suivante : : <math>\forall y \in \mathbb F_2^n \quad \hat f (y)={\mathcal F}(f)(\chi_y)=\frac 1{\sqrt {2^n}} \sum_{x\in{\mathbb{F}^n}}f(x){(-1)}^{x\cdot y}</math> On remarque que le signe ''moins'' utilisé dans la définition disparait car dans <math>\mathbb F_2</math> la multiplication par -1 est égale à l'identité. On remarque que la transformée de Walsh est [[idempotent]]e, c'est à dire qu'elle est égale à son inverse. On voit donc que l'un des intérêts de cette identification est d'avoir la transformation de Walsh et son inverse qui agissent sur les mêmes objets : des fonctions de <math>\mathbb{F}^n</math> dans <math>{\mathbb C}</math>. ====Formule de Poisson==== Un autre intérêt de l'identification de <math>\mathbb{F}_2^n</math> et de son dual, et non moins agréable que celui évoqué précédemment, est de simplifier considérablement la formule de Poisson. En effet, on obtient alors :<math>\sum_{u\in a+{\mathcal H}^\bot} {\hat f}(u) {(-1)}^{u\cdot b}= {(-1)}^{a\cdot b} |H^\bot| \cdot \sum_{u\in b+{\mathcal H}} f(u)(-1)^{a\cdot u}</math> On remarque que <math>{\mathcal H}^\bot</math> s'identifie naturellement à <math>\{z\in\mathbb F_2^n : \forall x\in H, z\cdot x=0 \}</math>. C'est ce qui est fait dans la formule ci-dessus, passant ainsi d'une notation multiplicative pour <math>{\mathcal H}^\bot</math> à une notation additive (on a également utilisé <math>b=-b</math> dans le cas de <math>\mathbb{F}_2^n</math>). On vérifie également que <math>{\mathcal H}</math> et <math>{\mathcal H}^\bot</math> sont des espaces vectoriels sur <math>\mathbb F_2</math>. ==Notes et références== ===Liens externes=== * {{fr}} [http://www.ufr-mi.u-bordeaux.fr/CSI/Cours/code.pdf Cours de code] par C. Bachoc Université de Bordeaux * {{fr}} [http://abdellah.bechata.free.fr/telechargement/harmonique/finis_commutatifs/pdf/fourier_groupe_fini.pdf Analyse harmonique sur les groupes finis commutatifs] par A. Bechata * {{fr}} [http://www.ufr-mi.u-bordeaux.fr/CSI/Cours/mathdis.pdf Mathématiques discrètes de la transformée de Fourier] C. Bachoc Université de Bordeaux I ===Références=== * Michel Demazure ''Cours d'algèbre. Primalité, divisibilité, codes'' Cassini 1997 * FJ MacWilliams & NJA Sloane ''The Theory of Error-Correcting Codes'' North-Holland, 1977 * A. Warusfel ''Structures algébriques finies'' Hachette 1971 * G. Peyré ''L'algèbre discrète de la transformée de Fourier'' Ellipses Marketing 2004 {{Portail|mathématiques|cryptologie}} [[Catégorie:Cryptologie]] [[Catégorie:Corps fini]] [[Catégorie:Théorie des codes]] [[Catégorie:Analyse harmonique discrète]] [[de:Boolesche Funktion]] [[en:Boolean function]] [[es:Función booleana]] [[fa:تابع بولی]] [[it:Funzione booleana]] [[ja:ブール関数]] [[ru:Булева функция]] [[zh:布尔函数]]