Issues on Computer Search for Large Order Multiple Recursive Generators
Identifieur interne : 000136 ( Main/Merge ); précédent : 000135; suivant : 000137Issues on Computer Search for Large Order Multiple Recursive Generators
Auteurs : Lih-Yuan Deng [États-Unis]Source :
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.
Url:
DOI: 10.1007/978-3-540-74496-2_14
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000206
- to stream Istex, to step Curation: 000205
- to stream Istex, to step Checkpoint: 000126
Links to Exploration step
ISTEX:A1963EB8E3FA9E87463FCD5C0DC887399097601ELe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Issues on Computer Search for Large Order Multiple Recursive Generators</title>
<author><name sortKey="Deng, Lih Yuan" sort="Deng, Lih Yuan" uniqKey="Deng L" first="Lih-Yuan" last="Deng">Lih-Yuan Deng</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:A1963EB8E3FA9E87463FCD5C0DC887399097601E</idno>
<date when="2008" year="2008">2008</date>
<idno type="doi">10.1007/978-3-540-74496-2_14</idno>
<idno type="url">https://api.istex.fr/document/A1963EB8E3FA9E87463FCD5C0DC887399097601E/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000206</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000206</idno>
<idno type="wicri:Area/Istex/Curation">000205</idno>
<idno type="wicri:Area/Istex/Checkpoint">000126</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000126</idno>
<idno type="wicri:Area/Main/Merge">000136</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Issues on Computer Search for Large Order Multiple Recursive Generators</title>
<author><name sortKey="Deng, Lih Yuan" sort="Deng, Lih Yuan" uniqKey="Deng L" first="Lih-Yuan" last="Deng">Lih-Yuan Deng</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Mathematical Sciences, University of Memphis, 38152, Memphis, TN</wicri:regionArea>
<placeName><region type="state">Tennessee</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Mathematiques/explor/SophieGermainV1/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000136 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 000136 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Mathematiques |area= SophieGermainV1 |flux= Main |étape= Merge |type= RBID |clé= ISTEX:A1963EB8E3FA9E87463FCD5C0DC887399097601E |texte= Issues on Computer Search for Large Order Multiple Recursive Generators }}
This area was generated with Dilib version V0.6.33. |