TY - JOUR

T1 - Aperiodic pseudorandom number generators based on infinite words

AU - Balková, Ľubomíra

AU - Bucci, Michelangelo

AU - De Luca, Alessandro

AU - Hladký, Jiří

AU - Puzynina, Svetlana

PY - 2016/9/27

Y1 - 2016/9/27

N2 - 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 v∈Zm d, there is an occurrence of w such that the Parikh vector of the prefix of u preceding such occurrence is congruent to v modulo m. (The Parikh vector of a finite word v over an alphabet A has its i-th component equal to the number of occurrences of the i-th letter of 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.

AB - 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 v∈Zm d, there is an occurrence of w such that the Parikh vector of the prefix of u preceding such occurrence is congruent to v modulo m. (The Parikh vector of a finite word v over an alphabet A has its i-th component equal to the number of occurrences of the i-th letter of 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.

KW - Arnoux–Rauzy word

KW - Linear congruential generator

KW - Pseudorandom number generator

KW - Sturmian word

KW - Well distributed occurrences

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

U2 - 10.1016/j.tcs.2016.07.042

DO - 10.1016/j.tcs.2016.07.042

M3 - Article

AN - SCOPUS:84995580487

VL - 647

SP - 85

EP - 100

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -