On the Approximation Errors in the Frequency Test Included in the NIST SP800-22 Statistical Test Suite

In previous papers we have addressed the problem of testing Random Number Generators (RNGs) through statistical tests, with particular emphasis on the approach we called second-level testing. We have shown that this approach is capable of achieving much higher accuracy in exposing non-random generators, but may suffer from reliability issues due to approximations introduced in the test. Here we consider the NIST Frequency Test and present a mathematical expression of the error introduced by approximating the effective discrete distribution function with its continuous limit distribution. The matching against experimental data is almost perfect. © 2008 IEEE.