Efficient parallel pseudorandom number generation
Publication
, Journal Article
Reif, JH; Tygar, JD
Published in: SIAM Journal on Computing
January 1, 1988
We present a parallel algorithm for pseudorandom number generation. Given a seed of nε truly random bits for any ε>0, our algorithm generates nc pseudorandom 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.
Duke Scholars
Published In
SIAM Journal on Computing
DOI
ISSN
0097-5397
Publication Date
January 1, 1988
Volume
17
Issue
2
Start / End Page
404 / 411
Related Subject Headings
- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics
Citation
APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Tygar, J. D. (1988). Efficient parallel pseudorandom number generation. SIAM Journal on Computing, 17(2), 404–411. https://doi.org/10.1137/0217024
Reif, J. H., and J. D. Tygar. “Efficient parallel pseudorandom number generation.” SIAM Journal on Computing 17, no. 2 (January 1, 1988): 404–11. https://doi.org/10.1137/0217024.
Reif JH, Tygar JD. Efficient parallel pseudorandom number generation. SIAM Journal on Computing. 1988 Jan 1;17(2):404–11.
Reif, J. H., and J. D. Tygar. “Efficient parallel pseudorandom number generation.” SIAM Journal on Computing, vol. 17, no. 2, Jan. 1988, pp. 404–11. Scopus, doi:10.1137/0217024.
Reif JH, Tygar JD. Efficient parallel pseudorandom number generation. SIAM Journal on Computing. 1988 Jan 1;17(2):404–411.
Published In
SIAM Journal on Computing
DOI
ISSN
0097-5397
Publication Date
January 1, 1988
Volume
17
Issue
2
Start / End Page
404 / 411
Related Subject Headings
- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics