Simultaneous Shifted Continued Fraction Expansions in Quadratic Time

In the theory of stream ciphers, important measures to assess the randomness of a given bit sequence are the linear and the jump complexity, both obtained from the continued fraction expansion (c.f.e.) of the generating function of the sequence. This paper describes a way to compute all continued fraction expansions (and thereby the linear complexity profiles, l.c.p.'s) of the shifted sequences , , , simultaneously in at most bit operations on bit space. If is not fixed beforehand, but varies during the computation, we have to start from . In this case we obtain the result in bit operations on space or as well in bit operations on linear space. In comparison, the well-known Berlekamp--Massey algorithm, when applied iteratively, needs O steps. A recent algorithm of Stephens and Lunnon works in O integer operations, but only gives the l.c.p., not the complete c.f.e. Received: April 29, 1996; revised version: November 3, 1997