Weight divisibility of cyclic codes, highly nonlinear functions on GF(2m) and crosscorrelation of maximum length sequences.


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

SIAM Journal of Discrete Mathematics, Vol. 13, No. 1, pp. 105-138. 2000.

Abstract

We study [2m-1,2m]-binary linear codes whose weights lie between w0 and 2m-w0, where w0 takes the highest possible value. Primitive cyclic codes with two zeros whose dual satisfy this property actually correspond to almost bent power functions and to pairs of maximum-length sequences with preferred crosscorrelation. We prove that, for odd m, these codes are completely characterized by their dual distance and by their weight divisibility. Using McEliece's theorem we give some general results on the weight divisibility of duals of cyclic codes with two zeros; we especially exhibit some infinite families of pairs of maximum-length sequences which are not preferred.

Keywords

cyclic codes, weight divisibility, Boolean functions, nonlinearity, almost bent functions, m-sequences, crosscorrelation.

PostScript and pdf versions