The probabilistic theory of linear complexity

From MaRDI portal





Let \(\mathbb F_q\) be the finite field of order \(q\) and let \(S\) be an arbitrary sequence of elements of \(\mathbb F_q\). If \(L_n(S)\) denotes the linear complexity of the first \(n\) terms of \(S\), then the sequence \(L_ 1(S)\), \(L_ 2(S),\ldots\) is called the linear complexity profile of \(S\). The aim of the paper is to study the linear complexity profile for random sequences \(S\). To arrive at a suitable probabilistic model, \(S\) is identified with its generating function and the Haar measure \(h\) on the compact abelian group of generating functions is used. It is shown that \(\lim_{n\to \infty}L_n(S)/n=h\text{-a.e.}\) Moreover, the deviations from the expected behavior are governed by the law of the logarithm: \[ \lim_{n\to \infty}\begin{matrix} \sup \\ \inf \end{matrix} \frac{L_n(S)-(n/2)}{\log n}=\pm \frac{1}{2 \log q}h\text{-a.e.} \] Further results pertain to the law of the iterated logarithm and the central limit theorem for perfect linear complexity and to frequency distributions for linear complexity. The proofs employ techniques from probability theory, topology, and the theory of dynamical systems. These probabilistic results are used as the basis for new types of randomness tests for keystream sequences. For the entire collection see [Zbl 0651.00027].




Cited in
(43)








This page was built for publication: The probabilistic theory of linear complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3807118)