Wilfried Meidl: On the linear complexity profile of explicit inversive pseudorandom number generators

The linear complexity and the linear complexity profile are important cryptographic characteristics of sequences $S$ over finite fields. A low linear complexity of a generator has turned out to be undesirable for more traditional applications in Monte Carlo methods as well. The concept of the linear complexity has also been generalized to vector sequences or multisequences, i.e. $m$ parallel sequences $S_1,\ldots, S_m$. We present some known and some new explicit inversive pseudorandom sequence and multisequence generators, and establish lower bounds on the linear complexity profiles of the sequences and multisequences produced by these generators. It turns out that several classes of explicit pseudorandom sequence generators produce sequences with a desirable linear complexity profile.

Back to the Index