Continued Fraction Expansion as Isometry – The Law of the Iterated Logarithm for Linear, Jump, and $2$-Adic Complexity
Michael Vielhaber · IEEE Transactions on Information Theory · 2007
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. Here, we define an isometry K on Fqinfinwhich is the precise equivalent to Euclid's algorithm over the reals to calculate the continued fraction expansion of a formal power series over Fqinfin. K allows us to deduce the linear and jump complexity profiles of the input sequence and since K is an isometry, the resulting Fqinfin-sequence is independent and identically distributed (i.i.d.) for i.i.d. input. Hence the linear and jump complexity profiles may be modeled via Bernoulli experiments. We thus can apply the precise bounds as collected by Revesz, among others the Law of the Iterated Logarithm The second topic is approximation by FCSR and AFSR registers, as defined by Goresky, Klapper, and Xu. For the 2-adic span, we derive an isometry A on F2infin. The corresponding jump complexity behaves on average exactly like coin tossing. Also, we give a general procedure to obtain an isometry from any approximation algorithm like LFSR, FCSR, or AFSR register synthesis. Focusing on the behavior of the result after applying the isometries instead of the complexities itself, permits us to apply the known bounds for Bernoulli experiments and to compare different complexities in a unified way, considering only their induced isometries. In this way, we can give sharp bounds on what behavior of the linear, jump, and 2-adic complexities is permitted for pseudorandom sequences, and what should be rejected.