On maximal period linear sequences and their crosscorrelation functions

Abstract

Mertebesi n olan ve sonlu Fp cismi üzerinde tanımlı bir doğrusal yinelemeli dizi içinmümkün en büyük period (pn ? 1)'dir. Periodu bu üst sınıra e³it olan böyle dizileremaksimum periodlu doğrusal diziler ya da kısaca m-dizileri denir. Bu tip dizilereolan ilgi uygulamalardan kaynaklanmı³tır. Gerçektende m-dizileri, kodlama teorisive şifreleme konuları devirsel kodlar, Boole fonksiyonları, vb. ilişkilerle yakın temashalindedirler. En önemli amaçlardan biri çapraz ilinti fonksiyonları az sayıda, ve tercihenküçük, değerlere sahip ikili m-diziler inşasıdır. Helleseth'in teoremine göre çaprazilinti fonksiyonu genelde en azından üç tane değere sahiptir. Dolayısıyla 3-değerliçapraz ilinti fonksiyonlarının varlığı ve in³ası çok ilgi uyandırır. Bu aynı zamandabizim çalışmamızın da ana temasıdır.Bu tezin amacı m-dizilerinin temel konularına giriş yapmak, yukarda bahsi geçendiğer konularla olan ilişkileri açıklamak ve 3-değerli çapraz ilinti fonksiyonlarının varlığıüzerine yapılmış üç farklı önsavın ispatlarını vermektir. Bu önsavlar Sarwate-Pursley,Helleseth ve Welch'e ait olup ispatları sırasıyla McGuire-Calderbank, Calderbank-McGuire-Poonen-Rubinstein ve Canteaut-Charpin-Dobbertin tarafından verilmiştir.

For an nth order linear recurring sequence over the nite eld Fp, the largest possibleperiod is pn ? 1. When such a sequence attains this upper bound as its period, it iscalled a maximal period linear sequence, or m-sequence in short. Interest in suchsequences originated from applications. Indeed, there is an interaction between msequences,coding theory and cryptography via the relation with cyclic codes, Booleanfunctions, etc. One of the main goals is to construct a pair of binary m-sequences whosecrosscorrelation takes few values, preferably with small magnitude. By a theorem ofHelleseth, the crosscorrelation function takes at least three values. Hence, existenceand 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, explainthe relations with other topics mentioned above, and to present proofs of three conjectureson the existence/nonexistence of 3-valued crosscorrelation functions for binarym-sequences. These conjectures are due to Sarwate-Pursley, Helleseth and Welch andwere proved by McGuire-Calderbank, Calderbank-McGuire-Poonen-Rubinstein andCanteaut-Charpin-Dobbertin respectively.