On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions (Q2370644)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions |
scientific article |
Statements
On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions (English)
0 references
29 June 2007
0 references
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.
0 references
linear complexity profile
0 references
nonlinear congruential generator
0 references
Redei functions
0 references
cryptography
0 references
0 references
0 references