Fonction booléenne

Une fonction booléenne est une fonction de $\mathbb{F}^n$ dans $\mathbb{F}$ où $\mathbb{F}$ désigne le corps fini à 2 éléments.

En fait, les fonctions booléennes sont simplement un autre nom des 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 boîtes-S, ainsi que dans les chiffrements par flot -- fonction de filtrage ou de combinaison de registres à décalage à rétroaction linéaire.

Sommaire

1 Propriétés
- 1.1 Forme algébrique normale
- 1.2 Linéarité et Non-linéarité
2 Outil d'étude : la transformée de Fourier
- 2.1 Cas d'un groupe abélien fini
- 2.2 Espace vectoriel sur le corps F₂
3 Voir aussi
- 3.1 Liens externes
- 3.2 Bibliographie

Propriétés

Forme algébrique normale

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 $n$ variables à coefficients dans $\mathbb{F}$ . Cependant, différents polynômes de $\mathbb{F}[X_0,...,X_{n-1}]$ donnent la même fonction. Par exemple, $X_0^2$ et $X_0^3$ donnent bien la même valeur lorsqu'ils sont évalués sur un élément de $\mathbb{F}^n$ . Pour obtenir une représentation unique, il faut considérer les éléments de l'anneau quotient, soit :

$\mathbb{F}[X_0,...,X_{n-1}]/(X_0^2+X_0,...,X_{n-1}^2+X_{n-1})$

Autrement dit, une fonction booléenne peut être représentée de manière unique par un polynôme de la forme :

$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}$

On pose fréquemment $u=(u_0,...,u_{n-1})~$ , $X=(X_0,...,X_{n-1})~$ et $X^u=\prod_{i=0}^{n-1}X_i^{u_i}$ , permettant l'écriture compacte :

$P(X)=\sum_{u\in\mathbb{F}^n} a_uX^u$ .

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 $\mathbb{F}^n$ -- vu comme espace sur le corps $\mathbb{F}$ . 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 :

$d_H(f,g) = \#\{u\in\mathbb{F}^n : f(u)\neq g(u)\}$

Les cryptographes utilisent le terme de non-linéarité pour parler de la distance d'une fonction booléenne à l'ensemble $\mathcal{A}$ des fonctions affines :

$\mathcal{N}(f)=\min \{d_H(f,g) : g\in \mathcal{A}\}$

L'intérêt de cette notion est de quantifier l'erreur commise si on remplace la fonction $f$ par une fonction affine : dans le meilleur des cas, on se « trompe » $\mathcal{N}(f)$ fois sur $2 n$ si $n$ 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

$\mathcal{N}(f)\le 2^{n-1}-2^{\frac{n}{2}-1}$

Lorsque $n$ 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 codes correcteurs, au point qu'il possède un nom, le code de Reed-Muller d'ordre $1$ (en $n$ variables). L'ordre est le degré maximal des fonctions. Ainsi, le code de Reed-Muller d'ordre $r~$ en $n~$ , usuellement noté $\mathrm{RM}(r,n)~$ est l'ensemble des fonctions en $n~$ variables de degré au plus $r~$ . Dans le contexte de la théorie des codes, la non-linéarité maximale se trouve correspondre au « rayon de recouvrement » du code $\mathrm{RM}(1,n)~$ , c'est-à-dire, la distance maximale entre un mot binaire de longueur $2 n$ et un mot du code.

Outil d'étude : la transformée de Fourier

La 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 cryptographiques comme la 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 FFT sert à décoder efficacement les 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 de 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 $\mathcal G$ en utilisant la notion de caractère. Un caractère $χ$ est un morphisme de $\mathcal G$ dans $\mathbb U$ , le groupe des racines de l'unité du corps des nombres complexes $\mathbb C$ .

L'ensemble des caractères opèrent sur l'ensemble des applications de $\mathcal G$ dans $\mathbb C$ , cet ensemble est appelé algèbre du groupe et est généralement noté $\mathbb C[\mathcal G]$ . Il est muni du produit hermitien suivant :

$\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)$

Ici si z est un complexe, z^* désigne son conjugué.

Les caractères forment une base orthonormale de l'algèbre du groupe.

L'ensemble des caractères de $\mathcal G$ peut être muni d'une structure de groupe en utilisant la multiplication entre applications, ce groupe est appelé le groupe dual. le groupe $\mathcal G$ et son dual son isomorphes si $\mathcal G$ est 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 $\mathcal G$ est 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 ${\mathcal G}$ une application du groupe dual $\mathcal F (\mathcal G)$ dans $\mathbb C$ notée ici ${\mathcal F}(f)$ et définie par :

$\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)^*$

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 $\mathbb K$ . 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 $\mathbb K$ , l'application χ de V dans son dual, qui à y associe le caractère χ_y définie par l'égalité suivante est cet isomorphisme :

$\forall x \in V \quad \chi_y(x) = \mu (y.x)$

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 :

$\forall \zeta \in V \quad {\mathcal F}(f)(\zeta)=\frac 1{\sqrt {|V|}}\sum_{x\in V}f(x)\mu(-\zeta.x)$

Espace vectoriel sur le corps F₂

Formes des caractères et isomorphisme avec le dual

On considère maintenant le cas où le corps $\mathbb K$ est celui à deux éléments noté $\mathbb F_2$ et l'espace vectoriel est $\mathbb F_2^n$ où n est un entier strictement positif. Soit x = (x_i) et y = (y_i) deux éléments de l'espace vectoriel, la forme bilinéaire . est définie par :

$x.y = \sum_{i=1}^n x_i.y_i$

Il n'existe que deux caractères dans $\mathbb F_2$ , le caractère trivial et celui qui à s associe (-1)^s. Comme il n'existe qu'un caractère non trivial, l'isomorphisme χ du paragraphe précédent prend la forme suivante :

$\forall x,y \in \mathbb F_2^n \quad \chi_y(x) = (-1)^{x.y}$

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 :

$\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}$

On remarque que le signe moins utilisé dans la définition disparait car dans $\mathbb F_2$ la multiplication par -1 est égale à l'identité. On remarque que la transformée de Walsh est idempotente, 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 $\mathbb{F}^n$ dans ${\mathbb C}$ .

Formule de Poisson

Un autre intérêt de l'identification de $\mathbb{F}_2^n$ 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

$\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}$

On remarque que ${\mathcal H}^\bot$ s'identifie naturellement à $\{z\in\mathbb F_2^n : \forall x\in H, z\cdot x=0 \}$ . C'est ce qui est fait dans la formule ci-dessus, passant ainsi d'une notation multiplicative pour ${\mathcal H}^\bot$ à une notation additive (on a également utilisé $b = - b$ dans le cas de $\mathbb{F}_2^n$ ). On vérifie également que ${\mathcal H}$ et ${\mathcal H}^\bot$ sont des espaces vectoriels sur $\mathbb F_2$ .

Voir aussi

Liens externes

Cours de code par Christine Bachoc, université Bordeaux I
Analyse harmonique sur les groupes finis commutatifs par A. Bechata
Mathématiques discrètes de la transformée de Fourier par C. Bachoc, université Bordeaux I
Groupes finis commutatifs et transformation de Fourier discrète par R. Rolland, Institut de Mathématiques de Luminy

Bibliographie

Michel Demazure, Cours d'algèbre. Primalité Divisibilité. Codes [détail des éditions]
(en) Jessie MacWilliams (en) et Neil Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977 (ISBN 978-0-444-85009-6)
André Warusfel, Structures algébriques finies, Éditions Hachette, 1971
G. Peyré, L'algèbre discrète de la transformée de Fourier, Éditions Ellipses, 2004

Catégories :

Cryptologie
Corps fini
Théorie des codes
Analyse harmonique discrète

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fonction booléenne de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Fonction Booléenne — Une fonction booléenne est une fonction de dans où désigne le corps fini à 2 éléments. En fait, les fonctions booléennes sont simplement un autre nom des fonctions logiques. Toutefois, lorsque l on s attache aux propriétés algébriques de ces… … Wikipédia en Français
Fonction booleenne — Fonction booléenne Une fonction booléenne est une fonction de dans où désigne le corps fini à 2 éléments. En fait, les fonctions booléennes sont simplement un autre nom des fonctions logiques. Toutefois, lorsque l on s attache aux propriétés… … Wikipédia en Français
fonction booléenne — Boolean funkcija statusas T sritis automatika atitikmenys: angl. Boolean connective; Boolean function vok. Boolesche Funktion, f; logische Funktion, f rus. булева связка, f; булева функция, f pranc. fonction booléenne, f; fonction de Boole, f… … Automatikos terminų žodynas
Fonction Courbe — Une fonction booléenne avec un nombre pair de variables est dite fonction courbe bent dans la terminologie anglosaxonne si sa non linéarité est maximale. Cela correspond à être à distance maximale pour la distance de Hamming de l ensemble des… … Wikipédia en Français
Fonction bent — Fonction courbe Une fonction booléenne avec un nombre pair de variables est dite fonction courbe bent dans la terminologie anglosaxonne si sa non linéarité est maximale. Cela correspond à être à distance maximale pour la distance de Hamming de l… … Wikipédia en Français
Fonction courbe — Une fonction booléenne avec un nombre pair de variables est dite fonction courbe bent dans la terminologie anglosaxonne si sa non linéarité est maximale. Cela correspond à être à distance maximale pour la distance de Hamming de l ensemble des… … Wikipédia en Français
fonction de Boole — Boolean funkcija statusas T sritis automatika atitikmenys: angl. Boolean connective; Boolean function vok. Boolesche Funktion, f; logische Funktion, f rus. булева связка, f; булева функция, f pranc. fonction booléenne, f; fonction de Boole, f… … Automatikos terminų žodynas
Fonction Logique — Pour les articles homonymes, voir combinatoire (homonymie). Cet article se place d emblée dans le cadre de la logique classique. Il existe deux grands types de fonctions logiques : les fonctions logiques « combinatoires », bases du … Wikipédia en Français
Fonction composée — Composition de fonctions En mathématiques, la composition de fonctions (ou composition d applications) est un procédé qui consiste, à partir de deux fonctions, d en construire une nouvelle. Pour cela on utilise les images de la première fonction… … Wikipédia en Français
Fonction logique — Pour les articles homonymes, voir combinatoire (homonymie). Il existe deux grands types de fonctions logiques : les fonctions logiques « combinatoires », bases du calcul booléen, qui résultent de l analyse combinatoire des… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Fonction booléenne

Sommaire