Couples de suites binaires de longueur maximale ayant une corrélation croisée à trois valeurs : conjecture de Welch.


Anne Canteaut
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Anne.Canteaut@inria.fr

Pascale Charpin
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Pascale.Charpin@inria.fr

Hans Dobbertin
German Information Security Agency
P.O.Box 20 03 63
D-53133 Bonn, Germany
dobbertin@skom.rhein.de

C.R. Acad. Sci. Paris, t. 328, Série I, p. 173-178, 1999.

Résumé

Nous prouvons une conjecture due à Welch, qui peut s'exprimer ainsi : la fonction a -> $\sum_{x \in GF(2^n)} (-1)^{tr(x^{2^m+3}+ax)}$, où a est dans GF(2^n), n=2m+1, et tr(u) est la trace de u dans GF(2^n) sur GF(2), prend exactement trois valeurs, qui sont 0, 2^{m+1} et -2^{m+1}. Ce résultat a diverses applications dans les télécommunications.

Abstract

We prove the long-standing conjecture of Welch stating that for odd n=2m+1 the function a -> $\sum_{x \in GF(2^n)} (-1)^{tr(x^{2^m+3}+ax)}$, where a is in GF(2^n) and tr(u) is the trace-function from GF(2^n) to GF(2), takes only three values, which are 0, 2^{m+1} and -2^{m+1}. This result widely applies in telecommunications