
Click here for full text:
Computing the Error Linear Complexity Spectrum of a Binary Sequence of Period 2n
Lauder, Alan; Paterson, Kenneth
HPL1999128R1
Keyword(s): cryptography; stream cipher; error linear complexity spectrum; algorithm; decoding; ReedMuller code
Abstract: Please Note. This abstract contains mathematical formulae which cannot be represented here. Binary sequences with high linear complexity are of interest in cryptography. The linear complexity should remain high even when a small number of changes are made to the sequence. The error linear complexity spectrum of a sequence reveals how the linear complexity of the sequence varies as an increasing number of the bits of the sequence are changed. We present an algorithm which computes the error linear complexity for binary sequences of period l=2n using 0 (l(log l)2) bit operations. The algorithm generalises both the Games Chan and StampMartin algorithms, which compute the linear complexity and the kerror linear complexity of a binary sequence of period l=2n , respectively. We also discuss an application of an extension of our algorithm to decoding a class of linear subcodes of ReedMuller codes. Notes: Alan Lauder, Junior Research Fellow at Wolfson College, Oxford, OX2 6UD and a member of the Mathematical Institute, Oxford University, Oxford, OX1 3LB, UK
13 Pages
Back to Index
