Linear complexity and linear complexity profile are important characteristics of a sequence for applications in cryptography and Monte-Carlo methods.
The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation.
Recently, a weak lower bound on the linear complexity profile of a general nonlinear congruential pseudorandom number generator was proven by Gutierrez, Shparlinski and the first author. For most nonlinear generators a much stronger lower bound is expected.
Here, we obtain a much stronger lower bound on the linear complexity profile of nonlinear congruential pseudorandom number generators with Dickson polynomials.