Binary m-sequences with three-valued crosscorrelation:
A proof of Welch conjecture.


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

IEEE Transactions on Information Theory, 46(1):4--8, 2000.

Abstract

We prove the long-standing conjecture of Welch stating that for odd n=2m+1, the power function x^d with d = 2^m+3 is maximally nonlinear on GF(2^n) or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequences of degree n and a decimation of that sequence by 2^m+3 takes on precisely the three values -1, -1 - 2^{m+1}, -1 + 2^{m+1}.

Keywords

Welch's conjecture, McEliece's Theorem, crosscorrelation, Walsh transform, power functions, almost perfect nonlinear mappings, maximally nonlinear mappings.