TY - JOUR

T1 - A Pseudo-Random Generator Whose Output is a Normal Sequence

AU - Ryabko, Boris

N1 - This work was supported by the Russian Foundation for Basic Research (grant 18-29-03005). Publisher Copyright: © 2021 World Scientific Publishing Company.

PY - 2021/12/1

Y1 - 2021/12/1

N2 - Pseudo-random number generators (PRNGs) are widely used in computer simulation, cryptography, and many other fields. In this paper, we describe a PRNG class, which, firstly, has been successfully tested using the most powerful modern test batteries, and secondly, is proved to consist of generators that generate normal sequences. The latter property means that, for any generated sequence x1x2... and any binary word w, we have limt→∞νt(w)/(t -|w|) = 2-|w|, where νt(w) is the number of occurrences of w in the sequence x1...x|w|, x2... x|w|+1,...,xt-|w|+1...xt.

AB - Pseudo-random number generators (PRNGs) are widely used in computer simulation, cryptography, and many other fields. In this paper, we describe a PRNG class, which, firstly, has been successfully tested using the most powerful modern test batteries, and secondly, is proved to consist of generators that generate normal sequences. The latter property means that, for any generated sequence x1x2... and any binary word w, we have limt→∞νt(w)/(t -|w|) = 2-|w|, where νt(w) is the number of occurrences of w in the sequence x1...x|w|, x2... x|w|+1,...,xt-|w|+1...xt.

KW - normal sequences

KW - Pseudo-random number generators

KW - randomness testing

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

U2 - 10.1142/S0129054121500325

DO - 10.1142/S0129054121500325

M3 - Article

AN - SCOPUS:85117072661

VL - 32

SP - 981

EP - 989

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 8

ER -