Continued Fraction Expansion as Isometry: The Law of the Iterated Logarithm for Linear, Jump, and 2--Adic Complexity

Details Continued Fraction Expansion as Isometry: The Law of the Iterated Logarithm for Linear, Jump, and 2--Adic Complexity Continued Fraction Expansion as Isometry: The Law of the Iterated Logarithm for Linear, Jump, and 2--Adic Complexity

2005-11-26

arxiv.org/abs/cs/0511089v1

Computer Science

Information Theory

32 pages Submitted (in revised form: 24 pages) to IEEE Transactions on Information Theory

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Continued Fraction Expansion as Isometry: The Law of the Iterated Logarithm for Linear, Jump, and 2--Adic Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Continued Fraction Expansion as Isometry: The Law of the Iterated Logarithm for Linear, Jump, and 2--Adic Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Continued Fraction Expansion as Isometry: The Law of the Iterated Logarithm for Linear, Jump, and 2--Adic Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-365200