hp home products & services support solutions how to buy
hp logo - invent
corner hp labs corner
search search
contact hp contact hp
hp labs home hp labs home
about hp labs about hp labs
research research
news and events news and events
careers @ labs careers @ labs
technical reports technical reports
talks and speeches talks and speeches
worldwide sites worldwide sites
corner corner
HP Labs Technical Reports

Click here for full text: Postscript PDF

Computing the Error Linear Complexity Spectrum of a Binary Sequence of Period 2n

Lauder, Alan; Paterson, Kenneth


Keyword(s): cryptography; stream cipher; error linear complexity spectrum; algorithm; decoding; Reed-Muller 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 Stamp-Martin algorithms, which compute the linear complexity and the k-error 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 Reed-Muller 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

printing icon
printing instructions printing instructions
Privacy Statement Legal Notices © 1994-2000 Hewlett-Packard Company