RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2011 Volume 23, Issue 1, Pages 51–71 (Mi dm1130)

This article is cited in 1 paper

On properties of the Klimov–Shamir generator of pseudorandom numbers

S. V. Rykov


Abstract: The pseudorandom number generator (PRNG) based on the transformation
$$ F_c(x)=x+(x^2\vee c)\pmod{2^n} $$
was suggested by Klimov and Shamir in 2002. The function $F_c(x)$ is transitive modulo $2^n$ if and only if either $c\equiv5\pmod8$ or $c\equiv7\pmod8$.
We consider properties of the distribution of the pairs $(x_i, F_c(x_i))$ for various $c\in\mathbf Z/2^n\mathbf Z$ and demonstrate that their statistical properties are unsatisfactory, most notably for $c\geq2^{n/3}$.
We show that in the case $n=32$, at most 9 distinct pairs $(x_i, F_c(x_i))$ are needed to find the value of $c$ with probability $P\geq0,999$.

UDC: 519.7

Received: 16.04.2010

DOI: 10.4213/dm1130


 English version:
Discrete Mathematics and Applications, 2011, 21:2, 179–202

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024