Predicting nonlinear pseudorandom number generators

Let p be a prime and let a and b be elements of the finite field double-struck F sign_p of p elements. The inversive congruential generator (ICG) is a sequence (u_n) of pseudorandom numbers defined by the relation u_n+1 = au_n^-1 + b mod p. We show that if sufficiently many of the most significant bits of several consecutive values u_n of the ICG are given, one can recover the initial value U₀ (even in the case where the coefficients a and b are not known). We also obtain similar results for the quadratic congruential generator (QCG), v_n+1 = f(v_n) mod p, where f ∈ double-struck F sign_p[X]. This suggests that for cryptographic applications ICG and QCG should be used with great care. Our results are somewhat similar to those known for the linear congruential generator (LCG), x_n+1 = ax_n + b mod p, but they apply only to much longer bit strings. We also estimate limits of some heuristic approaches, which still remain much weaker than those known for LCG.