Linear complexity can be used to detect predictable nonrandom sequences, and hence it is included in the NIST randomness test suite. But, as shown in this paper, the NIST test suite cannot detect nonrandom sequences that are generated, for instance, by concatenating two different M-sequences with low linear complexity. This defect comes from the fact that the NIST linear complexity test uses deviation from the ideal value only in the last part of the whole linear complexity profile. In this paper, a new faithful linear complexity test is proposed, which uses deviations in all parts of the linear complexity profile and hence can detect even the above nonrandom sequences. An efficient formula is derived to compute the exact area distribution needed for the proposed test. Furthermore, a simple procedure is given to compute the proposed test statistic from linear complexity profile, which requires only O(M) time complexity for a sequence of length M.

We propose a randomness test based on the T-complexity of a sequence, which can be calculated using a parsing algorithm called T-decomposition. Recently, the Lempel-Ziv (LZ) randomness test based on LZ-complexity using the LZ78 incremental parsing was officially excluded from the NIST test suite in NIST SP 800-22. This is caused from the problem that the distribution of P-values for random sequences of length 106 is strictly discrete for the LZ-complexity. Our proposed test can overcome this problem because T-complexity has almost ideal continuous distribution of P-values for random sequences of length 106. We also devise a new sequential T-decomposition algorithm using forward parsing, while the original T-decomposition is an off-line algorithm using backward parsing. Our proposed test can become a supplement to NIST SP 800-22 because it can detect several undesirable pseudo-random numbers that the NIST test suite almost fails to detect.

In this paper, the problem in the distribution of the test statistic of the Discrete Fourier Transform (DFT) test included in SP800-22 released by the National Institute of Standards and Technology (NIST), which causes a very high rate of rejection compared with the significance level, is considered on the basis of the distribution of the spectrum. The statistic of the DFT test, which was supposed to follow the standard normal distribution N(0, 1) according to the central limit theorem, seems to follow the normal distribution N(0.691, 0.5) approximately. The author derived the distribution function of the spectrum, and changed the threshold value from the default value of to the value of 1.7308 , where n is the length of a random number sequence. By this modification, the test statistic becomes to follow the normal distribution N(0, 0.5) approximately. The disagreement between this variance (= 0.5) and that of the standard normal distribution (= 1) can be considered to originate in the dependence of the spectrum. The evidences of the dependence are shown.

Accurate values for occurrence probabilities of the template used in the overlapping template matching test included in NIST randomness test suite (NIST SP800-22) have been analyzed. The inaccurate values used in the NIST randomness test suite cause significant difference of pass rate. When the inaccurate values are used and significance level is set to 1%, the experimental mean value of pass rate, which is calculated by use of random number sequences taken from DES (Data Encryption Standard), is about 98.8%. In contrast, our new values derived from a set of recurrence formulas for the NIST randomness test suite give an empirical distribution of pass rate that meets the theoretical binomial distribution. Here, the experimental mean value of pass rate is about 99%, which corresponds to the significance level 1%.