Computing the k-Error Linear Complexity of q-Ary Sequences with Period 2pn

Zhihua NIU  Zhe LI  Zhixiong CHEN  Tongjiang YAN  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E95-A   No.9   pp.1637-1641
Publication Date: 2012/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E95.A.1637
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Cryptography and Information Security
stream cipher,  periodic sequence,  linear complexity,  k-error linear complexity,  genetic algorithm,  

Full Text: PDF(213.6KB)>>
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. Recently, Zhou designed an algorithm for computing the k-error linear complexity of 2pn periodic sequences over GF(q). In this paper, we develop a genetic algorithm to confirm that one can't get the real k-error linear complexity for some sequenes by the Zhou's algorithm. Analysis indicates that the Zhou's algorithm is unreasonable in some steps. The corrected algorithm is presented. Such algorithm will increase the amount of computation, but is necessary to get the real k-error linear complexity. Here p and q are odd prime, and q is a primitive root (mod p2).