Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

So-called "perfect" or "unpredictable" pseudorandom generators have been proposed recently by people from the area of cryptology. Many people got aware of them from an optimistic article in the New York Times (Gleick (1988)). These generators are usually based on nonlinear recurrences modulo some integer m. Under some (yet unproven) complexity assumptions, it has been proven that no polynomial-time statistical test can distinguish a sequence of bits produced by such a generator from a sequence of truly random bits.In this paper, we give some theoretical background concerning this class of generators and we look at the practicality of using them for simulation applications. We examine in particular their ease of implementation, their efficiency, periodicity, the ease of jumping ahead in the sequence, the minimum size of modulus that should be used, etc.

REFERENCES

• 1: Alexi, W., Chor, B., Goldreich, O. and Schnorr, C. P. (1988). RSA and Rabin Functions: Certain Parts are as Hard as the Whole. SIAM J. on Computing, 17, 2, 194--209.
• 2: Beauchemin, P., Brassard, G., Crépeau, C., Goutier, C. and Pomerance, C. (1988). The Generation of Random Numbers That Are Probably Prime. J. of Cryptology, 1, 53--64.
• 3: Blum, L., Blum, M. and Schub, M. (1986). A Simple Unpredictable Pseudo-Random Number Generator. SIAM J. Comput., 15, 2, 364--383. Preliminary version published in Proceedings of CRYPTO 82, 61--78.
• 4: Blum, M. and Micali, S. (1984). How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SIAM J. on Computing, 13, 4, 850--864.
• 5: Boyar, J. (1989a). Missing Low Order Bits in a Linear Congruential Generator. To appear in J. of Cryptology.
• 6: Boyar, J. (1989b). Inferring Sequences Produced by Pseudo-Random Number Generators. J. of the ACM, 36, 1, 129--141.
• 7: Brassard, G. (1988). Modern Cryptology: A Tutorial. Lectures Notes in Computer Science, Springer-Verlag, New York.
• 8: Brassard, G. and Bratley P. (1987). Algorithmique, conception et analyse (in french), Masson, Paris, and Les Presses de l'Université de Montréal. English version: Algorithmics, Theory and Practice, Prentice-Hall, 1988.
• 9: Bratley, P., Fox, B. L. and Schrage, L. E. (1987). A Guide to Simulation, second edition. Springer-Verlag, New York.
• 10: Frieze, A. M., Kannan, R. and Lagarias, J. C. (1984). Linear Congruential Generators Do Not Produce Random Sequences. Proceedings of the 25th IEEE Symposium on Foundations of Computer Science, 480--484.
• 11: Frieze, A. M., Hastad, J., Kannan, R. and Lagarias, J. C. and Shamir, A. (1988). Reconstructing Truncated Integer Variables Satisfying Linear Congruences. SIAM J. on Computing, 17, 2, 262--280.
• 12: Gleick, J. (1988). The Quest for True Randomness Finally Appears Successful. The New York Times, Thuesday, April 19, 1988, C1 and C8.
• 13: Goldreich, O., Goldwasser, S. and Micali, S. (1986). How to Construct Random Functions. J. of the ACM, 33, 4, 792--807.
• 14: Knuth, D. E. (1981). The Art of Computer Programming : Seminumerical Algorithms, vol. 2, second edition. Addison-Wesley.
• 15: Lagarias, J. C. and Reeds, J. (1988). Unique Extrapolation of Polynomial Recurrences. SIAM J. on Computing, 17, 2, 342--362.
• 16: L'Ecuyer, P. (1988). Efficient and Portable Combined Random Number Generators. Communications of the ACM, 31, 6, 742--749 and 774.
• 17: L'Ecuyer, P. (1989). A Tutorial on Uniform Variate Generation. In these Proceedings.
• 18: L'Ecuyer, P., Perron, G. and Blouin, F. (1988). SENTIERS: Un logiciel Modula-2 pour I'arithmétique sur les grands entiers. Report no. DIUL-RT-8802, dépt. d'informatique, Univ. Laval.
• 19: Levin, L. A. (1987). One-Way Functions and Pseudorandom Generators. Combinatorica, 7, 4, 357--363.
• 20: Luby, M. and Rackoff, C. (1988). How to Construct Pseudorandom Permutations From Pseudorandom Functions. SIAM J. Computing, 17, 2, 373--386.
• 21: Micali, S. and Schnorr, C. P. (1988). Super-Efficient, Perfect Random Number Generators. Manuscript, Laboratory for Computer Science, M.I.T.
• 22: Morain, F. (1988). Implementation of the Atkin-Gold-wasser-Kilian Primality Testing Algorithm. Rapport de recherche no. 911, INRIA, Rocquencourt, France.
• 23: Plumstead, J. B. (Boyar) (1982). Inferring a Sequence Generated by a Linear Congruence. Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 153--159.
• 24: Rabin, M. O. (1979). Digitalized Signature and Public-Key Functions as Intractable as Factorization. Report no. MIT/LCS/TR-212, Laboratory for Computer Science, M.I.T., Cambridge.
• 25: Rabin, M. O. (1980). Probabilistic Algorithms for Primality Testing. J. Number Theory, 12, 128--138.
• 26: Reif, J. H. and Tygar, J. D. (1988). Efficient Parallel Pseudorandom Number Generation. SIAM J. Computing, 17, 2, 404--411.
• 27: Shamir, A. (1981). On the Generation of Cryptographically Strong Pseudo-Random Sequences. Proceedings of the 8th International Colloquium on Automata, Languages and Programming, Springer-Verlag, 544--550. Also in ACM Trans. on Computer Systems, 1, 1 (1983) 38--44.
• 28: Stern, J. (1987). Secret Linear Congruential Generators are not Cryptographically Secure. Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, 421--426.
• 29: Vazirani, U. and Vazirani, V. (1984). Efficient and Secure Pseudo-Random Number Generation. Proceedings of the 25th IEEE Symposium on Foundations of Computer Science, 458--463.
• 30: Vazirani, U. and Vazirani, V. (1983). Trapdoor Pseudo-Random Number Generators with Applications to Protocol Design. 15-th Annual ACM Symp. on Theory of Computing, 23--30.
• 31: Yao, A. C. (1982). Theory and Applications of Trapdoor Functions. Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 80--91.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Performance, Theory