Aperiodic pseudorandom number generators based on infinite words

详细信息    查看全文

• 作者：Ľubomí ; ra Balková ; ^a ; ^{lubomira.balkova@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Michelangelo Bucci^b ; ^{michelangelo.bucci@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Alessandro De Luca^c ; ^{alessandro.deluca@unina.it" class="auth_mail" title="E-mail the corresponding author} ; Jiří ; Hladký ; ^a ; ^{hladky.jiri@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Svetlana Puzynina^d ; ^e ; ^{s.puzynina@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Pseudorandom number generator ; Well distributed occurrences ; Sturmian word ; Arnoux&ndash ; Rauzy word ; Linear congruential generator
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：27 September 2016
• 年：2016
• 卷：647
• 期：Complete
• 页码：85-100
• 全文大小：648 K

文摘

In this paper we study how certain families of aperiodic infinite words can be used to produce aperiodic pseudorandom number generators (PRNGs) with good statistical behavior. We introduce the well distributed occurrences (WELLDOC) combinatorial property for infinite words, which guarantees absence of the lattice structure defect in related pseudorandom number generators. An infinite word u on a d-ary alphabet has the WELLDOC property if, for each factor w of u, positive integer m  , and vector class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516303875&_mathId=si1.gif&_user=111111111&_pii=S0304397516303875&_rdoc=1&_issn=03043975&md5=dd841cad301eb9bf6760be4e8c709242">class="imgLazyJSB inlineImage" height="17" width="42" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397516303875-si1.gif">class="mathContainer hidden">class="mathCode">$\mathbf{v}\in {\mathbb{Z}}_m^d$, there is an occurrence of w such that the Parikh vector of the prefix of u preceding such occurrence is congruent to class="boldFont">v modulo m. (The Parikh vector of a finite word v   over an alphabet class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516303875&_mathId=si2.gif&_user=111111111&_pii=S0304397516303875&_rdoc=1&_issn=03043975&md5=26ab482a7162780ac0e557655c96df50" title="Click to view the MathML source">Aclass="mathContainer hidden">class="mathCode">$\mathcal{A}$ has its i-th component equal to the number of occurrences of the i  -th letter of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516303875&_mathId=si2.gif&_user=111111111&_pii=S0304397516303875&_rdoc=1&_issn=03043975&md5=26ab482a7162780ac0e557655c96df50" title="Click to view the MathML source">Aclass="mathContainer hidden">class="mathCode">$\mathcal{A}$ in v.) We prove that Sturmian words, and more generally Arnoux–Rauzy words and some morphic images of them, have the WELLDOC property. Using the TestU01 [11] and PractRand [5] statistical tests, we moreover show that not only the lattice structure is absent, but also other important properties of PRNGs are improved when linear congruential generators are combined using infinite words having the WELLDOC property.