Continued Fraction Expansion as Isometry: The Law of the Iterated Logarithm for Linear, Jump, and 2--Adic Complexity
<|reference_start|>Continued Fraction Expansion as Isometry: The Law of the Iterated Logarithm for Linear, Jump, and 2--Adic Complexity: 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<|reference_end|>
@article{vielhaber2005continued,
    title={Continued Fraction Expansion as Isometry: The Law of the Iterated
  Logarithm for Linear, Jump, and 2--Adic Complexity},
    author={Michael Vielhaber},
    journal={arXiv preprint arXiv:cs/0511089},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0511089},
    primaryClass={cs.IT math.IT}
}