# zbMATH — the first resource for mathematics

Inferring sequences produced by pseudo-random number generators. (English) Zbl 0667.94006
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=\sum^{k}_{j=1}\alpha_ j\phi_ j(X_ 0,X_ 1,...,X_{n-1})(mod m).$$ In each case, we assume that the functions $$\phi_ j$$ are known and polynomial time computable, but that the coefficients $$\alpha_ j$$ 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.

##### MSC:
 94A60 Cryptography 65C10 Random number generation in numerical analysis
Full Text: