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

Pseudo-random numbers; Monte Carlo methods (11K45) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Cryptography (94A60)

Review text

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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2370644)