✦ LIBER ✦

Efficient, perfect polynomial random number generators

✍ Scribed by S. Micali; C. P. Schnorr

Publisher: Springer
Year: 1991
Tongue: English
Weight: 884 KB
Volume: 3
Category: Article
ISSN: 0933-2790
DOI: 10.1007/bf00196909

No coin nor oath required. For personal study only.

✦ Synopsis

Let N be a positive integer and let P E ZI-x] be a polynomial that is nonlinear on the set ZN of integers modulo N. If, by choosing x at random in an initial segment of Zs, P(x) (mod N) appears to be uniformly distributed in Zt; to any polynomial-time observer, then it is possible to construct very efficient pseudorandom number generators that pass any polynomial-time statistical test. We analyse this generator from two points of view. A complexity theoretic analysis relates the perfectness of the generator to the security of the RSA-scheme. A statistical analysis proves that the least-significant bits of P(x) (rood N) are statistically random.

📜 SIMILAR VOLUMES

Random-number generators

✍ Alan B. Forsythe 📂 Article 📅 1968 🏛 Elsevier Science 🌐 English ⚖ 217 KB

A commonly used uniform random-number generator is examined in light of a genetic-simulation problem. Although this generator is often useful, it proves defective in this case. The author suggests that any proposed generator be checked for the properties needed by the simulation problem at hand.

Portable random number generators

✍ Gerald P. Dwyer Jr.; K.B. Williams 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 67 KB

We present a random number generator that is useful for serious computations and can be implemented easily in any language that has 32-bit signed integers, for example C, C ++ and FORTRAN. This combination generator has a cycle length that would take two millennia to compute on widely used desktop c

Biometric random number generators

✍ J. Szczepanski; E. Wajnryb; J.M. Amigó; Maria V. Sanchez-Vives; M. Slater 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 169 KB

Up to now biometric methods have been used in cryptography for authentication purposes. In this paper we propose to use biological data for generating sequences of random bits. We point out that this new approach could be particularly useful to generate seeds for pseudo-random number generators and

Random number generators for microcomput

Random number generators for microcomputers

✍ Wilfred Rosenbaum; John Syrotuik; Richard Gordon 📂 Article 📅 1983 🏛 Elsevier Science ⚖ 331 KB

The feasibility of random number generation using microcomputers is discussed and the appropriateness of alternative algorithms is evaluated on the basis of several criteria of statistical randomness. The relative deficiencies of each algorithm are cited and a modified Fibonacci generator is recomme

Object oriented random number generators

✍ Joseph A. Fisher 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 269 KB

Testing parallel random number generator

Testing parallel random number generators

✍ Ashok Srinivasan; Michael Mascagni; David Ceperley 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 228 KB

Monte Carlo computations are considered easy to parallelize. However, the results can be adversely affected by defects in the parallel pseudorandom number generator used. A parallel pseudorandom number generator must be tested for two types of correlations--(i) intrastream correlation, as for any se