Efficient Parallel Pseudo-Random Number Generation
© 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. 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.).
Volume / Issue
Start / End Page
Electronic International Standard Serial Number (EISSN)
International Standard Serial Number (ISSN)
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)