Ryabko Boris
Institute of Computational Technologies of the Siberian Branch of the Russian Academy of Science, 630090 Novosibirsk, Russia.
Department of Information Technologies, Novosibirsk State University, 630090 Novosibirsk, Russia.
Entropy (Basel). 2020 Jun 7;22(6):630. doi: 10.3390/e22060630.
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 -values of tests. Namely, the theorem claims that, if the RNG can be modeled by a stationary ergodic source, the value - l o g π ( x 1 x 2 … x n ) / n goes to 1 - h when grows, where x 1 x 2 … is the sequence, π ( ) is the -value of the most powerful test, and is the limit Shannon entropy of the source.
本文考虑了为随机数生成器（RNG）构建有效统计检验的问题。目前，有数百种RNG统计检验，它们通常被组合成所谓的检验组，每个检验组包含从十几个到一百多个检验。当使用检验组进行检验时，会将其应用于RNG生成的序列，计算时间由序列长度和检验数量决定。一般来说，序列越长，特定检验所能发现的与随机性的偏差就越小。因此，当应用检验组时，一方面，检验组中的检验“越好”，拒绝“劣质”RNG的机会就越大。另一方面，检验组越大，每个检验所能花费的时间就越少，因此检验序列就越短。反过来，这又降低了发现与随机性微小偏差的能力。为了减少这种权衡，我们提出了一种自适应使用检验组（及其他检验集）的方法，该方法所需时间较少，但在某种意义上保留了原始检验组的功效。我们将这种方法称为时间自适应检验组。所提出的方法基于一个描述检验所谓p值渐近性质的定理。具体而言，该定理声称，如果RNG可以用平稳遍历源建模，当n增大时，值−logπ(x1x2…xn)/n趋于1−h，其中x1x2…是序列，π()是最强大检验的p值，h是源的极限香农熵。
