TY - JOUR

T1 - Large-order multiple recursive generators with modulus 231 - 1

AU - Deng, Lih Yuan

AU - Shiau, Jyh Jen Horng

AU - Lu, Henry Horng Shing

PY - 2012/9/1

Y1 - 2012/9/1

N2 - The performance of a maximum-period multiple recursive generator (MRG) depends on the choices of the recurrence order k, the prime modulus p, and the multipliers used. For a maximum-period MRG, a largeorder k not only means a large period length (i.e., pk - 1) but, more importantly, also guarantees the equidistribution property in high dimensions (i.e., up to k dimensions), a desirable feature for a good random-number generator. As to generating efficiency, in addition to the multipliers, some special choices of the prime modulus p can significantly speed up the generation of pseudo-random numbers by replacing the expensive modulo operation with efficient logical operations. To construct efficient maximum-period MRGs of a large order, we consider the prime modulus p = 231 - 1 and, via extensive computer search, find two large values of k, 71499 and 201897, for which pk - 1 can be completely factorized. The successful search is achieved with the help of some results in number theory as well as some modern factorization methods. A general class of MRGs is introduced, which includes several existing classes of efficient generators. With the factorization results, we are able to identify via computer search within this class many portable and efficient maximum-period MRGs of order 71499 or 201897 with prime modulus 231 - 1 and multipliers of powers-of-two decomposition. These MRGs all pass the stringent TestU01 test suite empirically.

AB - The performance of a maximum-period multiple recursive generator (MRG) depends on the choices of the recurrence order k, the prime modulus p, and the multipliers used. For a maximum-period MRG, a largeorder k not only means a large period length (i.e., pk - 1) but, more importantly, also guarantees the equidistribution property in high dimensions (i.e., up to k dimensions), a desirable feature for a good random-number generator. As to generating efficiency, in addition to the multipliers, some special choices of the prime modulus p can significantly speed up the generation of pseudo-random numbers by replacing the expensive modulo operation with efficient logical operations. To construct efficient maximum-period MRGs of a large order, we consider the prime modulus p = 231 - 1 and, via extensive computer search, find two large values of k, 71499 and 201897, for which pk - 1 can be completely factorized. The successful search is achieved with the help of some results in number theory as well as some modern factorization methods. A general class of MRGs is introduced, which includes several existing classes of efficient generators. With the factorization results, we are able to identify via computer search within this class many portable and efficient maximum-period MRGs of order 71499 or 201897 with prime modulus 231 - 1 and multipliers of powers-of-two decomposition. These MRGs all pass the stringent TestU01 test suite empirically.

KW - DX/DL/DS generators

KW - Equidistribution

KW - Pollard rho method

KW - Pollard's (p - 1) method

KW - Portable and efficient generators

KW - Primality testing

UR - http://www.scopus.com/inward/record.url?scp=84859533066&partnerID=8YFLogxK

U2 - 10.1287/ijoc.1110.0477

DO - 10.1287/ijoc.1110.0477

M3 - Article

AN - SCOPUS:84859533066

SN - 1091-9856

VL - 24

SP - 636

EP - 647

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

IS - 4

ER -