SCIENCE@home

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

F. Rodier

Published 2003 in Acta Arithmetica

ABSTRACT

Boolean functions on the space $F_{2}^m$ are not only important in the theory of error-correcting codes, but also in cryptography, wherethey occur in private key systems. In these two cases, the nonlinearity ofthese function is a main concept. In this article, I show that the spectral amplitude of booleanfunctions, which is linked to their nonlinearity, is of theorder of $2^{m/2}\sqrt{m}$ in mean, whereas its range is bounded by$2^{m/2}$ and$2^m$.Moreover I examine a conjecture of Patterson and Wiedemann saying that theminimum of this spectral amplitude is as close as desired to $2^{m/2}$.I also study a weaker conjecture about the moments of order 4 of theirFourier transform. This article is inspired by works of Salem, Zygmund,Kahane and others about the related problem of real polynomials withrandom coefficients.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-26 of 26 references · Page 1 of 1

CITED BY

Showing 1-19 of 19 citing papers · Page 1 of 1