The probabilistic theory of linear complexity
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].
- A combinatorial approach to probabilistic results on the linear- complexity profile of random sequences
- Linear Complexity and Random Sequences
- Keystream Sequences with a Good Linear Complexity Profile for Every Starting Point
- The linear complexity profile and the jump complexity of keystream sequences
- Linear complexity profiles: Hausdorff dimensions for almost perfect profiles and measures for general profiles
- On the relation between descriptional complexity and algorithmic probability
- Linear complexity profiles: Hausdorff dimensions for almost perfect profiles and measures for general profiles
- On the \(\delta \to 0\) limit in probabilistic complexity
- An analogue of a theorem of Szüsz for formal Laurent series over finite fields.
- On the pseudorandomness of automatic sequences
- Kronecker-Halton sequences in \(\mathbb{F}_p((X^{-1}))\)
- Perfect linear complexity profile and apwenian sequences
- Metrical properties for continued fractions of formal Laurent series
- Jump and hop randomness tests for binary sequences
- Pseudorandom sequences derived from automatic sequences
- Kurzweil type metrical Diophantine properties in the field of formal Laurent series
- Multidimensional linear complexity analysis of periodic arrays
- A linear-time algorithm for computing the multinomial stochastic complexity
- Cantor sets determined by partial quotients of continued fractions of Laurent series
- Enumeration results on linear complexity profiles and lattice profiles
- Continued fraction for formal Laurent series and the lattice structure of sequences
- Counting functions and expected values for the lattice profile at \(n\)
- On the relative growth rate of the product of consecutive partial quotients in continued fraction expansions of Laurent series
- Linear complexity and related complexity measures
- Keystream Sequences with a Good Linear Complexity Profile for Every Starting Point
- scientific article; zbMATH DE number 4045477 (Why is no real title available?)
- The linear complexity profile and the jump complexity of keystream sequences
- The independence of two randomness properties of sequences over finite fields
- Linear complexity versus pseudorandomness: On Beth and Dai's result
- On the quantitative metric theory of continued fractions in positive characteristic
- Probabilistic Recursion Theory and Implicit Computational Complexity
- The statistics of continued fractions for polynomials over a finite field
- On the Structure of Logspace Probabilistic Complexity Classes
- Expansion complexity and linear complexity of sequences over finite fields
- On sums of degrees of the partial quotients in continued fraction expansions of Laurent series
- On the joint linear complexity profile of explicit inversive multisequences
- Hausdorff dimension of the recurrence sets of Gauss transformation on the field of Laurent series
- Metrical properties for the weighted sums of degrees of multiple partial quotients in continued fractions of Laurent series
- On sets of exact Diophantine approximation over the field of formal series
- The metric properties of Sylvester continued fraction expansions over the field of formal Laurent series
- Some notes on the pseudorandomness of Legendre symbol and Liouville function
- Probabilistic results on the 2-adic complexity
- On metric Diophantine approximation in the field of formal Laurent series
- Probabilistic complexity analysis for linear problems in bounded domains
- Hausdorff dimensions of bounded-type continued fraction sets of Laurent series
- A combinatorial approach to probabilistic results on the linear- complexity profile of random sequences
- Beta-expansion and continued fraction expansion over formal Laurent series
- Enumeration results on the joint linear complexity of multisequences
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)