title: Linear complexity of polyphase power residue sequences
abstract: The well known family of binary Legendre or quadratic residue sequences can be generalised to the multiple-valued case by employing a polyphase representation. These p-phase sequences, with p prime, also have prime length L, and can be constructed from the index sequence of length L or, equivalently, from the cosets of pth power residues and non-residues modulo-L. The linear complexity of these polyphase sequences is derived and shown to fall into four classes depending on the value assigned to b/sub 0/, the initial digit of the sequence, and on whether p belongs to the set of pth power residues or not. The characteristic polynomials of the linear feedback shift registers that generate these sequences are also derived
keyphrases: linear complexity polyphase power residue sequences quadratic residue sequences multiple-valued case p-phase sequences polynomials linear feedback shift registers binary Legendre sequences cryptographic applications key stream ciphers binary sequences