Paper Info
Title
Linear Complexity of Periodic Sequences: A General Theory
Abstract
The linear complexity of an N-periodic sequence with components in a field of characteristic p, where N = npϕ and gcd(n, p) = 1, is characterized in terms of the nth roots of unity and their multiplicities as zeroes of the polynomial whose cofficients are the first N digits of the sequence. Hasse derivatives are then introduced to quantify these multiplicities and to define a new generalized discrete Fourier transform that can be applied to sequences of arbitrary length N with components in a field of characteristic p, regardless of whether or not gcd(N, p) = 1. This generalized discrete Fourier transform is used to give a simple proof of the validity of the well-known Games-Chan algorithm for finding the linear complexity of an N-periodic binary sequence with N = 2ϕ and to generalize this algorithm to apply to N-periodic sequences with components in a finite field of characteristic p when N = pϕ. It is also shown how to use this new transform to study the linear complexity of Hadamard (i.e., component-wise) products of sequences.
Year
DOI
Venue
1996
10.1007/3-540-68697-5_27
CRYPTO
Keywords
Field
DocType
generalized discrete fourier,well-known games-chan algorithm,n digit,linear complexity,finite field,n-periodic binary sequence,hasse derivative,n-periodic sequence,periodic sequences,new generalized discrete fourier,characteristic p,general theory,hadamard product,roots of unity,discrete fourier transform,stream cipher
Discrete mathematics,Combinatorics,Finite field,Polynomial,Root of unity,Pseudorandom binary sequence,Discrete Fourier transform (general),Discrete Fourier transform,Fractional Fourier transform,Hadamard transform,Mathematics
Conference
ISBN
Citations 
PageRank 
3-540-61512-1
23
2.05
References 
Authors
6
2
Name
Order
Citations
PageRank
James L. Massey11096272.94
Shirlei Serconek2544.94