| Philippe Langevin |  |
 |
Date de l'exposé : 24 janvier 2003
Sur la Conjecture de Patterson-Wiedeman
La distance d'une fonction booléenne f de m variables au code de Reed-Muller est une mesure la non-linearité de f. Il s'agit d'une notion importante en cryptographie. L'analyse de Fourier est une méthode d'approche normale de cette question. En particulier, la non-linéarité de f est égale à[ 2^m - R(f) ] /2,
où R(f) est l'amplitude spectrale de f i.e. le module maximal de ses coefficients de Fourier.
Un des problèmes majeurs consiste à déterminer la valeur minimale (rayon spectral) de R(f) lorsque f décrit l'ensemble de toutes les fonctions booléennes, équivalent à déterminer le rayon de recouvrement du code de Reed-Muller du premier ordre.
Le rayon spectral est facile à calculer lorsque m est pair, il est réalisé par les fonctions quadratiques non-dégénérée. Le cas impair est encore ouvert, sauf pour les petites valeurs de m : 3, 5 et 7.
Dans les années 80, Paterson-Wiedemann ont découvert une fonction booléenne de 15 variables moins linéaire que les fonctions quadratiques : contre-exemple à une conjecture formulée dans les années 70 par Mykkelveit.
Au cours de mon exposé, je montrerai d'autres contre-exemples plus linéaire mais mieux structurés construits à partir des sommes de Gauss. Enfin, je discuterai de la conjecture de Patterson et Wiedemann qui affirme l'équivalence asympototique entre le rayon spectral R(m) et 2^{m/2}. Philippe Langevin, janvier 2003.
