Continued Fraction Expansion as Isometry – The Law of the Iterated Logarithm for Linear, Jump, and 2-Adic Complexity
From MaRDI portal
Publication:3548978
DOI10.1109/TIT.2007.907499zbMATH Open1325.94145arXivcs/0511089OpenAlexW2001756903MaRDI QIDQ3548978FDOQ3548978
Authors: Michael Vielhaber 
Publication date: 21 December 2008
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: In the cryptanalysis of stream ciphers and pseudorandom sequences, the notions of linear, jump, and 2-adic complexity arise naturally to measure the (non)randomness of a given string. We define an isometry K on F_q^infty that is the precise equivalent to Euclid's algorithm over the reals to calculate the continued fraction expansion of a formal power series. The continued fraction expansion allows to deduce the linear and jump complexity profiles of the input sequence. Since K is an isometry, the resulting F_q^infty-sequence is i.i.d. for i.i.d. input. Hence the linear and jump complexity profiles may be modelled via Bernoulli experiments (for F_2: coin tossing), and we can apply the very precise bounds as collected by Revesz, among others the Law of the Iterated Logarithm. The second topic is the 2-adic span and complexity, as defined by Goresky and Klapper. We derive again an isometry, this time on the dyadic integers Z_2 which induces an isometry A on F_2}^infty. The corresponding jump complexity behaves on average exactly like coin tossing. Index terms: Formal power series, isometry, linear complexity, jump complexity, 2-adic complexity, 2-adic span, law of the iterated logarithm, Levy classes, stream ciphers, pseudorandom sequences
Full work available at URL: https://arxiv.org/abs/cs/0511089
Cited In (1)
This page was built for publication: Continued Fraction Expansion as Isometry – The Law of the Iterated Logarithm for Linear, Jump, and $2$-Adic Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548978)
