Parallel linear congruential generators with prime moduli

摘要

Linear congruential generators(LCGs)remain the most popular method of pseudorandom number generation on digital computers. Ease of implementation has favored implementing LCGs with power-of-two moduli. However, 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 becomes as even more compelling issue. We Use a full-period exponential sum as the measure of stream independence and present a method for Producing provably independent streams of LCGs in parallel by utilizing an eplicit parameteriza- Tion of all of the primitive elements modulo a given prime.