Sum-discrepancy test on pseudorandom number generators
We introduce a non-empirical test on pseudorandom number generators (prng), named sum-discrepancy test. We compute the distribution of the sum of consecutive m outputs of a ping to be tested, under the assumption that the initial state is uniformly randomly chosen. We measure its discrepancy from the ideal distribution, and then estimate the sample size which is necessary to reject the generator. These tests are effective to detect the structure of the outputs of multiple recursive generators with small coefficients, in particular that of lagged Fibonacci generators such as random() in BSD-C library, as well as add-with-carry and subtract-with-borrow generators like RCARRY The tests show that these generators will be rejected if the sample size is of order 10(6). We tailor the test to generators with a discarding procedure, such as ran-array and RANLUX, and exhibit empirical results. It is shown that ran_array with half of the output discarded is rejected if the sample size is of the order of 4 x 10(10). RANLUX with luxury level I (i.e. half of the output discarded) is rejected if the sample size is of the order of 2 x 10(8), and RANLUX with luxury level 2 (i.e. roughly 3/4 is discarded) will be rejected for the sample size of the order of 2.4 x 10(18). In our previous work, we have dealt with the distribution of the Hamming weight function using discrete Fourier analysis. In this work, we replace the Hamming weight with the continuous sum, using a classical Fourier analysis, i.e. Poisson's summation formula and Levy's inversion formula. (C) 2002 IMACS. Published by Elsevier Science B.V. All rights reserved.
random number generation statistical test fourier transform