Inferring sequences produced by pseudo-random number generators

In this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators. The generators considered are all of the form X n = Σ k j-l α j φ j ( X o , X l , . . ., X n-l ) (mod m ). In each case, we assume that the functions φ j are known and polynomial time computable, but that the coefficients aj and the modulus m are unknown. Using this general method, specific examples of generators having this form, the linear congruential method, linear congruences with n terms in the recurrence, and quadratic congruences are shown to be cryptographically insecure.