Summary: We present a parallel algorithm for pseudorandom number generation. Given a seed of \(n^{\epsilon}\) truly random bits for any \(\epsilon >0\), our algorithm generates n c pseudorandom bits for any \(c>1\). This takes poly- log time using \(n^{\epsilon '}\) processors where \(\epsilon '=k\epsilon\) 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. The proof is interesting and is quite different from previous proofs for sequential pseudorandom 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 \textit{D. E. Knuth}'s: The art of computer programming, Vol. 2: Seminumerical algorithms (1981; Zbl 0477.65002). Moreover, the existence of our generator has a number of central consequences for complexity theory. Given a randomized parallel algorithm \({\mathcal 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 that \({\mathcal A}\) can be simulated by a parallel algorithm with time bound \(T(n)+O((\log n)(\log \log n))\), processor bound \(P(n)n^{\epsilon '}\), and only using \(n^{\epsilon}\) truly random bits for any \(\epsilon >0.\) Also, we show that if the Multiplicative Inverse Problem is almost always not in RNC, the RNC is within the class of languages accepted by uniform poly-log depth circuits with unbounded fan-in and strictly subexponential size \(\cap_{\epsilon >0}2^{n^{\epsilon}}\).