Geodesic
On properties of the Klimov--Shamir generator of pseudorandom numbers
Diskretnaya Matematika, Tome 23 (2011) no. 1, pp. 51-71

Voir la notice de l'article provenant de la source Math-Net.Ru

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$. 
@article{DM_2011_23_1_a4,
     author = {S. V. Rykov},
     title = {On properties of the {Klimov--Shamir} generator of pseudorandom numbers},
     journal = {Diskretnaya Matematika},
     pages = {51--71},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2011_23_1_a4/}
}
TY  - JOUR
AU  - S. V. Rykov
TI  - On properties of the Klimov--Shamir generator of pseudorandom numbers
JO  - Diskretnaya Matematika
PY  - 2011
SP  - 51
EP  - 71
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2011_23_1_a4/
LA  - ru
ID  - DM_2011_23_1_a4
ER  - 
%0 Journal Article
%A S. V. Rykov
%T On properties of the Klimov--Shamir generator of pseudorandom numbers
%J Diskretnaya Matematika
%D 2011
%P 51-71
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2011_23_1_a4/
%G ru
%F DM_2011_23_1_a4
S. V. Rykov. On properties of the Klimov--Shamir generator of pseudorandom numbers. Diskretnaya Matematika, Tome 23 (2011) no. 1, pp. 51-71. http://geodesic.mathdoc.fr/item/DM_2011_23_1_a4/