Pseudorandom numbers. (English) Zbl 0766.65003

Probability and algorithms, 65-85 (1992).
[For the entire collection see Zbl 0755.00002.]
The author surveys problems in generating and using pseudorandom numbers. He deals with some general principles for constructing pseudorandom bit generators and its underlying group-theoretic or number-theoretic structure. Some pseudorandom bit generators are described explicitly.
The author describes the subject of computational information theory and its connection to cryptography. The basic object in this theory is the concept of a secure pseudorandom bit generator. Essential properties of pseudorandom generators, especially of secure pseudorandom bit generators, are described. Results on the statistical performance of various known pseudorandom number generators are discussed with respect to suitability for cryptographic uses. It is shown that a special pseudorandom bit generator, called the RSA generator, produces secure pseudorandom bits if the problem of factoring certain integers is computationally difficult.


65C10 Random number generation in numerical analysis
94A60 Cryptography
11K45 Pseudo-random numbers; Monte Carlo methods


Zbl 0755.00002