RESSOURCES EN LIGNE ET ACTUALITÉS
SCIENTIFIQUES FRANCOPHONES

3165 - Sur la non-linéarité des fonctions booléennes

Description bibliographique

Auteur :

Rodier, François (Université de la Méditerranée, Aix-Marseille 2. IML. Institut de mathématiques de Luminy. France)

Éditeur :

Université de la Méditerranée, Aix-Marseille 2. IML. Institut de mathématiques de Luminy. France

Page source :

Publications de l'IML, http://iml.univ-mrs.fr/editions

Langue :

français

Date de publication :

2002/04/26

Description du contenu

Spécialité :

Sciences exactes - Mathématiques - Arithmétique

Mots clés :

rayon de recouvrement ; cryptographie ; fonction booléenne ; transformation de Fourier

Table des matières :

1 - Introduction
2 - Préliminaires
3 - L'espace des fonctions booléennes à une infinité de variables
4 - Etude de $\|\bar{f}\|_\infty$
5 - Etude de $\|\bar{f}\|_4$
Références

Résumé :

L'amplitude spectrale des fonctions booléennes sur l'ensemble $F_2^m$, liée à leur non-linéarité, est comprise entre $2^{m/2}$ et $2^m$. On montre dans cet article que la valeur moyenne de cette amplitude spectrale est de l'ordre de $2^{m/2}\sqrt{m}$. De plus, on discute une conjecture suivant laquelle le minimum de cette amplitude spectrale s'approcherait autant qu'on le veut de $2^{m/2}$. (résumé d'auteur)

Accès à la ressource

Format :

PDF
Taille du fichier : entre 100 et 500 ko

Notes :

Document de 20 pages, également disponible au format PostScript.

URL de référence :

http://iml.univ-mrs.fr/editions/preprint2002/files/FonctBool.pdf

Notice mise en ligne le 28/02/2003