Publications [#236917] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH; Tygar, JD, Efficient parallel pseudorandom number generation, SIAM Journal on Computing, vol. 17 no. 2 (January, 1988), pp. 404-411, Society for Industrial & Applied Mathematics (SIAM) [doi]
   (last updated on 2026/01/14)

   Abstract:
   We present a parallel algorithm for pseudorandom number generation. Given a seed of n^ε truly random bits for any ε>0, our algorithm generates n^c 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/n^O(1) if the Multiplicative Inverse Problem almost always cannot be solved in RNC.