Issues on Computer Search for Large Order Multiple Recursive Generators

Lih-Yuan Deng ()
Additional contact information
Lih-Yuan Deng: University of Memphis, Department of Mathematical Sciences

A chapter in Monte Carlo and Quasi-Monte Carlo Methods 2006, 2008, pp 251-261 from Springer

Abstract: Summary Multiple Recursive Generators (MRGs) have become the most popular random number generators recently. They compute the next value iteratively from the previous k values using a k-th order recurrence equation which, in turn, corresponds to a k-th degree primitive polynomial under a prime modulus p. In general, when k and p are large, checking if a k-th degree polynomial is primitive under a prime modulus p is known to be a hard problem. A common approach is to check the conditions given in Alanen and Knuth [1964] and Knuth [1998]. However, as mentioned in Deng [2004], this approach has two obvious problems: (a) it requires the complete factorization of p k - 1, which can be difficult; (b) it does not provide any early exit strategy for non-primitive polynomials. To avoid (a), one can consider a prime order k and prime modulus p such that (p k - 1)/(p - 1) is also a prime number as considered in L’Ecuyer [1999] and Deng [2004]. To avoid (b), one can use a more efficient iterative irreducibility test proposed in Deng [2004]. In this paper, we survey several leading probabilistic and deterministic methods for the problems of primality testing and irreducibility testing. To test primality of a large number, it is known that probabilistic methods are much faster than deterministic methods. On the other hand, a probabilistic algorithm in fact has a very tiny probability of, say, 10-200 to commit a false positive error in the test result. Moreover, even when such an unlikely event had happened, for a speci.c choice of k and p, it can be argued that such an error has a negligible e.ect on the successful search of a primitive polynomial. We perform a computer search for large-order DX generators proposed in Deng and Xu [2003] and present many such generators in the paper for ready implementation. An extensive empirical study shows that these large-order DX generators have passed the stringent Crush battery of the TestU01 package.

Keywords: Prime Number; Random Number Generator; Irreducible Polynomial; False Positive Error; Primitive Polynomial (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-74496-2_14

Ordering information: This item can be ordered from
http://www.springer.com/9783540744962

DOI: 10.1007/978-3-540-74496-2_14

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().