SIMULTANEOUS SHIFTED CONTINUED-FRACTION EXPANSIONS IN QUADRATIC TIME

In the theory of stream ciphers, important measures to assess the rand omness of a given bit sequence (a(1), ..., a(n)) are the linear and th e jump complexity, both obtained from the continued fraction expansion (c.f.e.) of the generating function of the sequence. This paper descr ibes a way to compute all continued fraction expansions (and thereby t he linear complexity profiles, l.c.p.'s) of the n shifted sequences (a (n)), (a(n-1), a(n)), ..., (a(1), ..., a(n)) simultaneously in at most 4.5 . (n(2) + n) bit operations on n + 3 + 2 . inverted right perpend icular log(2) n inverted left perpendicular bit space. If n is not fix ed beforehand, but varies during the computation, we have to start fro m a(1). In this case we obtain the result in 4.5 . (n(2) + n) bit oper ations on 2 . n . inverted right perpendicular log(2) n inverted left perpendicular + 3 . n space or as well in 9.5 . (n(2) + n) bit operati ons on linear 4 . n + 2. inverted right perpendicular log(2) n inverte d left perpendicular + 1 space. In comparison, the well-known Berlekam p-Massey algorithm, when applied iteratively, needs O(n(3)) steps. A r ecent algorithm of Stephens and Lunnon works in O(n(2)) integer operat ions, but only gives the l.c.p., not the complete c.f.e.