Sur la non-linearite des fonctions booleennes

Details Sur la non-linearite des fonctions booleennes Sur la non-linearite des fonctions booleennes

2003-06-27

arxiv.org/abs/math/0306395v1

Mathematics

Number Theory

Scientific paper

Boolean functions on the space $F_{2}^m$ are not only important in the theory of error-correcting codes, but also in cryptography, where they occur in private key systems. In these two cases, the nonlinearity of these function is a main concept. In this article, I show that the spectral amplitude of boolean functions, which is linked to their nonlinearity, is of the order 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 the minimum 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 their Fourier transform. This article is inspired by works of Salem, Zygmund, Kahane and others about the related problem of real polynomials with random coefficients.

Affiliated with

Also associated with

No associations

Rating

Sur la non-linearite des fonctions booleennes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sur la non-linearite des fonctions booleennes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sur la non-linearite des fonctions booleennes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-335498