Publications [#330504] of John H. Reif

Conference articles PUBLISHED

1. Reif, JH; Tygar, JD, Efficient Parallel Pseudo-Random Number Generation, edited by H. Williams and E. Brickell, Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 218 LNCS (January, 1986), pp. 433-446, Springer Berlin Heidelberg, ISBN 9783540164630 (Presented at the Mathematical Theory of Security, Boston, MA, 1985.) [pdf], [doi]
   (last updated on 2026/02/08)

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