Some improvements to statistical tests of randomness using pattern matching


  • Hoang Dinh Linh
  • Tran Thi Luong



randomness testing, template matching, 5-bit, 4-bit

Tóm tắt

Tóm tắt—Các kiểm tra liên quan đến so khớp mẫu chồng lấp đã được đề xuất trong NIST SP 800-22 [1], tuy nhiên các xác suất trong các kiểm tra này chỉ đúng cho các mẫu đặc biệt và cần được tính lại cho các mẫu khác. Trong [2], các tác giả đã đề xuất các tiêu chuẩn thống kê so khớp mẫu mới cho tất cả các mẫu 4 bit. Các kiểm tra mới này áp dụng cho chuỗi bất kỳ có độ dài tối thiểu là 5504 bit, trong khi theo NIST độ dài tối thiểu 106 bit. Trong bài báo này, chúng tôi đã cải tiến và đề xuất các kiểm tra so khớp mẫu 4 bit mới mà có thể áp dụng cho các chuỗi bất kỳ có độ dài nhỏ nhất chỉ là 3726 bit. Hơn nữa, chúng tôi đưa ra 3 kiểm tra thống kê so khớp mẫu 5 bit mới. Kết quả lý thuyết và thực hành cho thấy các đề xuất cải tiến của chúng tôi là rất hiệu quả trong việc đánh giá tính ngẫu nhiên cho các bộ tạo số giả ngẫu nhiên.

AbstractRandomness tests related to overlapping template matching have been proposed in NIST SP 800-22 [1], however the probabilities in these tests are only valid for specific samples and should be recalculated for other samples. In [2], the authors proposed new template matching tests for all 4-bit templates. The new tests can be applied to any sequence of minimum length of 5504 bits whereas the overlapping template matching test in the NIST test suite can only be applied to sequences of minimum length of 106 bits. In this paper, we have modified and proposed new 4-bit template matching tests that can be applied to any sequence of minimum length 3726 bits. Furthermore, we proposed three new 5-bit template matching tests. Our theoretical and practical results show that our new proposed tests are very efficient in psedorandom number generator testing.


Download data is not yet available.


Bassham III, L.E., et al., SP 800-22 Rev. 1a. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, National Institute of Standards & Technology, Gaithersburg, MD, 2010.

Sulak, F., New statistical randomness tests: 4-bit template matching tests. Turkish Journal of Mathematics, 41(1), 2017, p. 80-95.

Oorschot, P.v., Vanstone, S.A., and MENEZES, A., Handbook of applied cryptography, CRC press, 1997.

Kunuth, D., The Art of Computer Programming vol. 2 Seminumerical Algorithms, Reading, Massachusetts: Addison Wesley, 1998.

Caelli, W., Crypt x package documentation. Information Security Research Centre School of Mathematics, Queensland University of Technology, 1992.

Marsaglia, G., The marsaglia random number cdrom including the diehard battery of tests of randomness, 2008 (Accessed 19/8/2021).

L'Ecuyer, P. and Simard, R., TestU01: AC library for empirical testing of random number generators. ACM Transactions on Mathematical Software (TOMS), 33(4), 2007, p. 22.

Menezes, A.J., Van Oorschot, P., and Vanstone, S., Handbook of Applied Cryptography, CRCPress, Chapter. 5(7), 1996, p. 12.

Soto, J. and Bassham, L., Randomness testing of the advanced encryption standard finalist candidates. 2000.

Sulak, F., et al. Evaluation of randomness test results for short sequences. in International Conference on Sequences and Their Applications. Springer, 2010.

Takeda, Y., The problem of template matching test in the testing randomness by NIST. IEICE Technical Report, 2005, p. ISEC2005-110.

Doğanaksoy, A. and Göloğlu, F. On Lempel-Ziv complexity of sequences. in International Conference on Sequences and Their Applications. Springer, 2006.

Doganaksoy, A. and Tezcan, C. An alternative approach to Maurer’s universal statistical test. in Information Security and Cryptology Conference ISC Turkey 2006 3rd International Conference Proceedings. 2008.

Okutomi, H., A study on the randomness evaluation method using NIST randomness test. Proc. SCIS, Jan., 2006.

Hamano, K. and Kaneko, T., Correction of overlapping template matching test included in NIST randomness test suite. IEICE transactions on fundamentals of electronics, communications and computer sciences, 2007. 90(9): p. 1788-1792.

Rukhin, A., et al., Statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST special publication. 2010.

Charalambides, C.A., Enumerative combinatorics., Chapman and Hall/CRC, 1996.

Hoang Dinh Linh, "Some results on new statistical randomness tests based on length of runs", Journal of Science and Technology on Information security, ISSN 2615-9570, Vol. 08, No. 02, 2018, pp. 19-24.

Adrián Alfonso Peñate, Daymé Almeida Echevarria, Laura Castro Argudín, “Statistical Assessment of two Rekeying Mechanisms applied to the Generation of Random Numbers”, Journal of Science and Technology on Information Security, ISSN 2615-9570, Vol. 12, No. 02, 2020, pp. 38-44.


Abstract views: 132 / PDF downloads: 47


2022-01-12 — Updated on 2022-01-12

How to Cite

Linh, H. D., & Lượng, T. T. (2022). Some improvements to statistical tests of randomness using pattern matching. Journal of Science and Technology on Information Security, 1(13), 49-61.