On maximal period linear sequences and their crosscorrelation functions
Canan Kaşıkçı · Sabanci University · 2006
For an nth order linear recurring sequence over the finite field Fp. the largest possible period is pn --- 1. When such a sequence attains this upper bound as its period, it is called a maximal period linear sequence, or m-sequence in short. Interest in such sequences originated from applications. Indeed, there is an interaction between m-sequences, coding theory and cryptography via the relation with cyclic codes.Boolean functions, etc. One of the main goals is to construct a pair of binary m-sequences whose crosscorrelation takes few values, preferably with small magnitude. By a theorem of Helleseth. the crosscorrelation function takes at least three values.Hence, existence and construction of sequences with 3-valued crosscorrelation is of particular interest. This is also the main theme of our work. The aim of this thesis is to introduce foundational material on m-sequences, explain the relations with other topics mentioned above, and to present proofs of three conjectures on the existence/nonexistence of 3-valued crosscorrelation functions for binary m-sequences. These conjectures are due to Sarwate-Pursley, Helleseth and Welch and were proved by McGuire-Calderbank. Calderank-MeGnire-Poonen-Rubinstein and. Canteaut-Charpin-Dobbertin respectively.