A Randomness Test Based on T-Complexity
Kenji Hamano and Hirosuke Yamamoto
- We propose a randomness test based on the Tcomplexity 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 10^6 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 10^6. We also devise a new sequential Tdecomposition 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.
- Index Terms: T-code, T-complexity, Lempel-Ziv complexity, NIST SP 800-22, NIST statistical test suite, multiplicative congruential generator
- PDF (713Kbytes) Copyright(c) 2010 IEICE
DOI: 10.1587/transfun.E93.A.1346