# Efficient Parallel Pseudo-Random Number Generation

Published

Conference Paper

© 1986, Springer-Verlag Berlin Heidelberg. We present a parallel algorithm for pseudo-random number generation. Given a seed of n ε truly random bits for any ε > 0, our algorithm generates n c pseudo-random bits for any c > 1. This takes poly-log time using n ε′ processors where ε′ = κε for some fixed small constant κ > 1. We show that the pseudo-random bits output by our algorithm can not be distinguished from truly random bits in parallel poly-log time using a polynomial number of processors with probability 1/2 + 1/n O(1) if the multiplicative inverse problem almost always can not be solved in RNC. The proof is interesting and is quite different from previous proofs for sequential pseudo-random number generators. Our generator is fast and its output is provably as effective for RNC algorithms as truly random bits. Our generator passes all the statistical tests in Knuth[14]. Moreover, the existence of our generator has a number of central consequences for complexity theory. Given a randomized parallel algorithm A (over a wide class of machine models such as parallel RAMs and fixed connection networks) with time bound T(n) and processor bound P(n), we show A can be simulated by a parallel algorithm with time bound T(n) + O((log n)(log log n)), processor bound P(n)n ε′, and only using n ε truly random bits for any ε > 0. Also, we show that if the multiplicative inverse problem is almost always not in RNC, then RNC is within the class of languages accepted by uniform poly-log depth circuits with unbounded fan-in and strictly sub-exponential size (Formula presented.).

### Full Text

### Duke Authors

### Cited Authors

- Reif, JH; Tygar, JD

### Published Date

- January 1, 1986

### Published In

### Volume / Issue

- 218 LNCS /

### Start / End Page

- 433 - 446

### Electronic International Standard Serial Number (EISSN)

- 1611-3349

### International Standard Serial Number (ISSN)

- 0302-9743

### International Standard Book Number 13 (ISBN-13)

- 9783540164630

### Digital Object Identifier (DOI)

- 10.1007/3-540-39799-X_33

### Citation Source

- Scopus