A Randomness Test Based on T-Complexity

作者：Hamano Kenji^*; Yamamoto Hirosuke

来源：IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 2010, E93A(7): 1346-1354.

DOI：10.1587/transfun.E93.A.1346

• T-code
• T-complexity
• Lempel-Ziv complexity
• NIST SP 800-22
• NIST statistical test suite
• multiplicative congruential generator

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 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 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.

• 出版日期2010-7