TY - JOUR

T1 - Time-adaptive statistical test for random number generators

AU - Ryabko, Boris

PY - 2020/6/1

Y1 - 2020/6/1

N2 - The problem of constructing effective statistical tests for random number generators (RNG) is considered. Currently, there are hundreds of RNG statistical tests that are often combined into so-called batteries, each containing from a dozen to more than one hundred tests. When a battery test is used, it is applied to a sequence generated by the RNG, and the calculation time is determined by the length of the sequence and the number of tests. Generally speaking, the longer is the sequence, the smaller are the deviations from randomness that can be found by a specific test. Thus, when a battery is applied, on the one hand, the "better" are the tests in the battery, the more chances there are to reject a "bad" RNG. On the other hand, the larger is the battery, the less time it can spend on each test and, therefore, the shorter is the test sequence. In turn, this reduces the ability to find small deviations from randomness. To reduce this trade-off, we propose an adaptive way to use batteries (and other sets) of tests, which requires less time but, in a certain sense, preserves the power of the original battery. We call this method time-adaptive battery of tests. The suggested method is based on the theorem which describes asymptotic properties of the so-called p-values of tests. Namely, the theorem claims that, if the RNG can be modeled by a stationary ergodic source, the value -log π(x1x2...xn)/n goes to 1-h when n grows, where x1x2... is the sequence, π( ) is the p-value of the most powerful test, and h is the limit Shannon entropy of the source.

AB - The problem of constructing effective statistical tests for random number generators (RNG) is considered. Currently, there are hundreds of RNG statistical tests that are often combined into so-called batteries, each containing from a dozen to more than one hundred tests. When a battery test is used, it is applied to a sequence generated by the RNG, and the calculation time is determined by the length of the sequence and the number of tests. Generally speaking, the longer is the sequence, the smaller are the deviations from randomness that can be found by a specific test. Thus, when a battery is applied, on the one hand, the "better" are the tests in the battery, the more chances there are to reject a "bad" RNG. On the other hand, the larger is the battery, the less time it can spend on each test and, therefore, the shorter is the test sequence. In turn, this reduces the ability to find small deviations from randomness. To reduce this trade-off, we propose an adaptive way to use batteries (and other sets) of tests, which requires less time but, in a certain sense, preserves the power of the original battery. We call this method time-adaptive battery of tests. The suggested method is based on the theorem which describes asymptotic properties of the so-called p-values of tests. Namely, the theorem claims that, if the RNG can be modeled by a stationary ergodic source, the value -log π(x1x2...xn)/n goes to 1-h when n grows, where x1x2... is the sequence, π( ) is the p-value of the most powerful test, and h is the limit Shannon entropy of the source.

KW - Hypothesis testing

KW - p-value

KW - Random number generators

KW - Randomness testing

KW - Test battery

KW - hypothesis testing

KW - random number generators

KW - randomness testing

KW - test battery

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

U2 - 10.3390/E22060630

DO - 10.3390/E22060630

M3 - Article

C2 - 33286402

AN - SCOPUS:85088270391

VL - 22

JO - Entropy

JF - Entropy

SN - 1099-4300

IS - 6

M1 - 630

ER -