Linear congruential generators (LCGs) remain the most popular method o
f pseudorandom number generation on digital computers. Ease of impleme
ntation has favored implementing LCGs with power-of-two moduli. Howeve
r, prime modulus LCGs are superior in quality to power-of-two modulus
LCGs, and the use of a Mersenne prime minimizes the computational cost
of generation. When implemented for parallel computation, quality bec
omes an even more compelling issue. We use a full-period exponential s
um as the measure of stream independence and present a method for prod
ucing provably independent streams of LCGs in parallel by utilizing an
explicit parameterization of all of the primitive elements module a g
iven prime. The minimization of this measure of independence further m
otivates an algorithm required in the explicit parameterization. We de
scribe and analyze this algorithm and describe its use in a parallel L
CG package. (C) 1998 Elsevier Science B.V. All rights reserved.