A Randomness Test Based on T-Complexity

スポンサーリンク

概要

• 論文の詳細を見る

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

• 2010-07-01

著者

• Yamamoto Hirosuke

  Department Of Complexity Science And Engineering Graduate School Of Frontier Science The University

• Hamano Kenji

  Department Of Complexity Science And Engineering The University Of Tokyo

関連論文

• Strongly Secure Linear Network Coding
• THE UTILITY OF DOBUTAMINE (DOB) STRESS ECG
• A Randomness Test Based on T-Complexity
• A New Randomness Test Based on Linear Complexity Profile
• The Optimal n-out-of-n Visual Secret Sharing Scheme for Gray-Scale Images(Special Section on Information Theory and Its Applications)
• Correction of Overlapping Template Matching Test Included in NIST Randomness Test Suite(Information Theory and Its Applications)
• A CASE OF OCULAR TOXOPLASMOSIS IN AN ADULT, THE INFECTION BEING CONFIRMED BY THE ISOLATION OF THE PARASITE FROM SUBRETINAL FLUID

スポンサーリンク