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$.