On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions (Q2370644)

Let \((s_n)\) be an infinite sequence over the finite field \(\mathbb{F}_p\) with \(p\) elements, where \(p\) is a prime. The linear complexity profile \(L(s_n,N)\) of \((s_n)\) is a function that, for \(N\geq 2\), is defined as the length \(L\) of a shortest linear recurrence relation, \[ s_{n+L}=a_{L-1}s_{n+L-1}+\cdots +a_0 s_n,\;0\leq n\leq N-L-1, \] where \(a_0,\ldots,a_{L-1}\in\mathbb{F}_p\), satisfied by \((s_n)\). The authors of the paper study the linear complexity profile of certain nonlinear congruential pseudorandom number generators. Bounds on the linear complexity profile, either for general cases or for certain subclasses of these generators, have been obtained in preceding papers. In this article, the authors consider the special case of nonlinear congruential pseudo-random number generators with Rédei functions. For a sequence \((u_n)\) generated by such a pseudo-random number generator, the authors show the bound \[ L(u_n,N)\geq \frac{\min\left\{N^2,4T^2\right\}}{20(p+1)^{3/2}},\;N\geq 2, \] where \(T\) is the period of the sequence.