A Randomness Test Based on T-Complexity

DOI Web Site 被引用文献1件 参考文献41件
  • HAMANO Kenji
    Department of Complexity Science and Engineering, The University of Tokyo
  • YAMAMOTO Hirosuke
    Department of Complexity Science and Engineering, The University of Tokyo

この論文をさがす

説明

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.

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (41)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ