Analysis of the Linear Complexity and Its Stability for 2pn-Periodic Binary Sequences

Zhihua NIU  Guozhen XIAO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.9   pp.2412-2418
Publication Date: 2005/09/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.9.2412
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
stream ciphers,  periodic sequences,  linear complexity,  k-error linear complexity,  polynomial weight,  

Full Text: PDF(166KB)>>
Buy this Article

The linear complexity and its stability of periodic sequences are of fundamental importance as measure indexes on the security of stream ciphers and the k-error linear complexity reveals the stability of the linear complexity properly. The k-error linear complexity of periodic sequences is defined to be the smallest linear complexity that can be obtained by changing k or fewer bits of the sequence per period. For 2pn-periodic binary sequences, where p is an odd prime and 2 is a primitive root modulo p2, we present and prove the unique expression of the linear complexity. Moreover we show a relationship between the linear complexity and the minimum value k for which the k-error linear complexity is strictly less than the linear complexity.