Please use this identifier to cite or link to this item: https://doi.org/10.1006/jcom.2001.0621
Title: Linear complexity, k-error linear complexity, and the discrete Fourier transform
Authors: Meidl, W.
Niederreiter, H. 
Keywords: Discrete Fourier transform
k-error linear complexity
Linear complexity
Periodic sequences
Issue Date: 2002
Citation: Meidl, W., Niederreiter, H. (2002). Linear complexity, k-error linear complexity, and the discrete Fourier transform. Journal of Complexity 18 (1) : 87-103. ScholarBank@NUS Repository. https://doi.org/10.1006/jcom.2001.0621
Abstract: Complexity measures for sequences of elements of a finite field play an important role in cryptology. We focus first on the linear complexity of periodic sequences. By means of the discrete Fourier transform, we determine the number of periodic sequences S with given prime period length N and linear complexity LN,0(S) = c as well as the expected value of the linear complexity of N-periodic sequences. Cryptographically strong sequences should not only have a large linear complexity, but also the change of a few terms should not cause a significant decrease of the linear complexity. This requirement leads to the concept of the k-error linear complexity LN,k(S) of sequences S with period length N. For some k and c we determine the number of periodic sequences S with given period length N and LN,k(S) = c. For prime N we establish a lower bound on the expected value of the k-error linear complexity. © 2002 Elsevier Science (USA).
Source Title: Journal of Complexity
URI: http://scholarbank.nus.edu.sg/handle/10635/103493
ISSN: 0885064X
DOI: 10.1006/jcom.2001.0621
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

39
checked on Aug 14, 2018

WEB OF SCIENCETM
Citations

28
checked on Aug 7, 2018

Page view(s)

39
checked on Aug 3, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.