Efficient parallel pseudorandom number generation


Journal Article

We present a parallel algorithm for pseudorandom number generation. Given a seed of nεtruly random bits for any ε>0, our algorithm generates ncpseudorandom bits for any c>1. This takes poly-log time using nε′processors where ε′=kε for some fixed small constant k>1$/. We show that the pseudorandom bits output by our algorithm cannot be distinguished from truly random bits in parallel poly-log time using a polynomial number of processors with probability 1/2 +1/nO(1)if the Multiplicative Inverse Problem almost always cannot be solved in RNC.

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Tygar, JD

Published Date

  • January 1, 1988

Published In

Volume / Issue

  • 17 / 2

Start / End Page

  • 404 - 411

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/0217024

Citation Source

  • Scopus