## Efficient Parallel Pseudo-Random Number Generation

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.).

### Duke Scholars

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Start / End Page

## Related Subject Headings

- Artificial Intelligence & Image Processing
- 46 Information and computing sciences

### Citation

*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*(Vol. 218 LNCS, pp. 433–446). https://doi.org/10.1007/3-540-39799-X_33

*Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, 218 LNCS:433–46, 1986. https://doi.org/10.1007/3-540-39799-X_33.

*Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, vol. 218 LNCS, 1986, pp. 433–46.

*Scopus*, doi:10.1007/3-540-39799-X_33.

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Start / End Page

## Related Subject Headings

- Artificial Intelligence & Image Processing
- 46 Information and computing sciences