Issues on Computer Search for Large Order Multiple Recursive Generators

摘要: Multiple Recursive Generators (MRGs) have become the most popular random number generators recently. They compute next value iteratively from previous k values using a k-th order recurrence equation which, in turn, corresponds to degree primitive polynomial under prime modulus p. In general, when and p are large, checking if is known be hard problem. A common approach check conditions given Alanen Knuth [1964] [1998]. However, as mentioned Deng [2004], this has two obvious problems: (a) it requires complete factorization of - 1, which can difficult; (b) does not provide any early exit strategy for non-primitive polynomials. To avoid (a), one consider such that (p 1)/(p 1) also considered L’Ecuyer [1999] [2004]. (b), use more efficient iterative irreducibility test proposed