How to Predict Congruential Generators

In this paper we show how to predict a large class of pseudorandom number generators. We consider congruential generators which output a sequence of integers s₀,s₁,... where s_i is computed by the recurrence 1$$ s_i \equiv \sum\limits_{j = 1}^k {\alpha _j \Phi _j (s_0 ,s_1 , \cdots ,s_{i - 1} )(\bmod m)} $$ for integers m and α_j, and integer functions Φ_j, j= 1,...,k. Our predictors are efficient, provided that the functions Φ_j are computable (over the integers) in polynomial time. These predictors have access to the elements of the sequence prior to the element being predicted, but they do not know the modulus m or the coefficients α_j the generator actually works with. This extends previous results about the predictability of such generators. In particular, we prove that multivariate polynomial generators, i.e. generators. where s_i ≡ P(s_i-n,..., s_i-1) (mod m), for a polynomial P of fixed degree in n variables, are efficiently predictable.