On the linear complexity and the linear complexity profiles of sequences in finite fields

Abstract

ÖZET Dizi şifreleyicilerde kullanılan yarı rasgele dizilerin rasgelelik ve öngörülememezlik özelliklerine sahip olmaları gerekir. Doğrusal karmaşıklık profili bu özellikleri ölçmede kullanılan önemli bir araçtır. Bu tezde dizilerin doğrusal karmaşıklığı ve doğrusal karmaşıklık profili üzerinde son yıllarda elde edilen bazı önemli sonuçlar sunulmaktadır. Özellike, Bir sonlu cisim üzerinde verilen bir fonksiyonun polinomsal derecesiyle doğrusal karmaşıklığı arasındaki bağlantı, `üstsel` ve `kendini küçülten` üreteçlerin doğrusal karmaşıklık sınırları ve doğrusal karmaşıklığı yüksek dizilerin oluşturulma yöntemleri üzerindeki çalışmalar incelenmiştir. Anahtar kelimeler: Doğrusal indirgemeli diziler, doğrusal karmaşıklık, doğrusal karmaşıklık profili.

ABSTRACT Pseudo random sequences, that are used for stream ciphers, are required to have the properties of unpredictability and randomness. An important tool for measuring these features is the linear complexity profile of the sequence in use. In this thesis we present a survey of some recent results obtained on linear complexity and linear complexity profile of pseudo random sequences. The relation between the polynomial degree and the linear complexity of a function over a finite field is given, bounds for linear complexity of the `power generator` and `the self- shrinking generator` are presented and a new method of construction of sequences of high linear complexity profile is illustrated. Key words : Linear recurrence sequences, linear complexity, linear complexity profile