Authors

Statistical g-test for random number generators

Random number generators produce numbers with the uniform distribution, and there is no correlation between these numbers that would allow to predict the generated number better than random guessing. Such generators are used in various tasks, such as modeling or information security. Hardware devices that transform a random physical process into a data stream are used as generators. Another type of generators are software generators that use a formula or algorithm to obtain a new number. It is believed that software generators, although they work faster, but do not have a proven property of randomness. There are a number of known cases when patterns were found in such generators, which led to the refusal to use them. There are test sets for checking the generator exists. If all tests are successfully passed, the generator is recommended for use. The purpose of this article is to develop an algorithm for testing bit sequences for randomness. In this paper, a new algorithm for testing random number generators is proposed, that can be included in the general set of statistical tests required for verification. Unlike previously known tests based on the entropy approach, the new test uses autocorrelation of the generated data. It is shown that the proposed test allows one to identify deviations from randomness in generators that have previously passed known statistical tests. During the experiments, the output sequences of the cipher, hash function and some pseudo-random number generators were tested. As the analysis of the test results showed, some generators have autocorrelation in the generated data. The idea of the test is that any generator has a period when all numbers from the generated set (alphabet) are appeared in the sequence. In the ideal case, the period will be close to the size of the alphabet or will be slightly larger. However, if some symbols are repeated more often, the period will increase significantly. In other words, an increase in the period may indicate either a deviation from a uniform distribution or the presence of autocorrelation in the generated data. The latter phenomenon is the area of interest this article. In this research we use elements of probability theory and mathematical statistics. The experiments were conducted on a large volume of the generated sequence of numbers. Read more...