The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.7 pp.1346-1354

- Publication Date
- 2010/07/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E93.A.1346

- Type of Manuscript
- PAPER

- Category
- Cryptography and Information Security

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Kenji HAMANO, Hirosuke YAMAMOTO, "A Randomness Test Based on T-Complexity" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 7, pp. 1346-1354, July 2010, doi: 10.1587/transfun.E93.A.1346.

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

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.1346/_p

Copy

@ARTICLE{e93-a_7_1346,

author={Kenji HAMANO, Hirosuke YAMAMOTO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={A Randomness Test Based on T-Complexity},

year={2010},

volume={E93-A},

number={7},

pages={1346-1354},

abstract={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.},

keywords={},

doi={10.1587/transfun.E93.A.1346},

ISSN={1745-1337},

month={July},}

Copy

TY - JOUR

TI - A Randomness Test Based on T-Complexity

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1346

EP - 1354

AU - Kenji HAMANO

AU - Hirosuke YAMAMOTO

PY - 2010

DO - 10.1587/transfun.E93.A.1346

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E93-A

IS - 7

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - July 2010

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

ER -