Alev Topuzoglu: On the nonlinear pseudorandom number generators of higher orders

This is a joint work with Arne Winterhof.

Nonlinear congruential pseudorandom number generators have been studied extensively in the last decades because of the well known deficiencies of the classical linear congruential generators. It is shown that the sequences generated by nonlinear methods have favourable behaviour. In this talk we shall report on some recent results on the properties of pseudorandom number generators defined by a recurrence relation of order $m\ge 2$,

$$u_{n+1}= f(u_n, u_{n-1}, \ldots , u_{n-m+1}), n = m-1, m, \ldots$$

Here initial values $u_0 , \ldots , u_{m-1}$ are in the finite field $\mathbb{F}_p$ with prime $p$ and $f$ is a rational function in $m$ variables over $\mathbb{F}_p$. Nonlinear generators of higher order $m$ are of particular interest as the period length of generated sequences can go up to $p^m$.

Bibliography

1

Jaime Gutierrez, Igor E. Shparlinski, and Arne Winterhof.
On the linear and nonlinear complexity profile of nonlinear pseudorandom number-generators.
IEEE Trans. Inform. Theory, 49(1):60-64, 2003.

2

Harald Niederreiter and Igor E. Shparlinski.
On the distribution and lattice structure of nonlinear congruential pseudorandom numbers.
Finite Fields Appl., 5(3):246-253, 1999.

3

Alev Topuzoglu and Arne Winterhof.
On the linear complexity profile of nonlinear congruential generators of higher orders.
(submitted).

Back to the Index