The DOI matches its Crossref record; 18 of the 19 references it cites were found in a registry or an index.
Study on upper limit of sample size for a two-level test in NIST SP800-22
Abstract
NIST SP800-22 is one of the most widely used statistical testing tools for pseudorandom number generators (PRNGs). This tool consists of 15 tests (one-level tests) and two additional tests (two-level tests). Each one-level test provides one or more p-values. The two-level tests measure the uniformity of the obtained p-values for a fixed one-level test. One of the two-level tests categorizes the p-values into ten intervals of equal length, and apply a chi-squared goodness-of-fit test. This two-level test is often more powerful than one-level tests, but sometimes it rejects even good PRNGs when the sample size at the second level is too large, since it detects approximation errors in the computation of p-values.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator
Matsumoto, M., & Nishimura, T. (1998) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/272991.272995 · Cited by 5,780 · cited 1×
“e second row of Table 1 and other test parameters are initial values in NIST SP800-22. In order to justify the name of the risky/safe sample sizes, we apply the twolevel test to Mersenne Twister (MT) [11] and a PRNG from SHA-1 algorithm (SHA-1) with ve dierent initial random seeds. We take the second sample sizes appr…”
MethodThe Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · The American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,822
Bassham, L. E., Rukhin, A. L., Soto, J., Nechvatal, J. R., Smid, M. E., Barker, E. B., Leigh, S. D., Levenson, M., Vangel, M., Banks, D. L., et al. (2010) · NIST Special Publication 800-22 Revision 1a · doi:10.6028/nist.sp.800-22r1a · Cited by 3,617 · cited 1×
“In this paper, we investigate the test suite, named SP80022, proposed by National Institute of Standards and Technology (NIST) [1] for pseudorandom bit generators (PRBGs).”
MethodTestU01: A C library for empirical testing of random number generators
L'Ecuyer, P., & Simard, R. (2007) · ACM Transactions on Mathematical Software · doi:10.1145/1268776.1268777 · Cited by 1,014 · cited 1×
“over the interval [0;1], or over the integers in an interval (e.g. f0;1g). There are many statistical tests for PRNGs, for example, TestU01 by L’Ecuyer and Simard is the most comprehensive test suite [10], and recently PractRands [2] is published. In this paper, we investigate the test suite, named SP800- 22, proposed…”
MethodShiryaev, A. N. (1996) · Graduate texts in mathematics · doi:10.1007/978-1-4757-2539-1 · Cited by 834
Improved long-period generators based on linear recurrences modulo 2
Panneton, F., L'Ecuyer, P., & Matsumoto, M. (2006) · ACM Transactions on Mathematical Software · doi:10.1145/1132973.1132974 · Cited by 283 · cited 1×
“e results are N 0:25 = 3;785 and N 0:0001 = 46;084. Table 8 shows p-values of the two-level test with the sample sizes 3;700, 18;600, 46;100 and 211;000. In the experiments, we test on SHA-1 and WELL [13]. These results indicate that the Monte Carlo simulation give an approximation value of with enough accuracy in pra…”
MethodUniform random number generation
L'Ecuyer, P. (1994) · Annals of Operations Research · doi:10.1007/bf02136827 · Cited by 279 · cited 1×
“d level makes the two-level test makes reliable: we can maximize the power and avoid erroneous rejections of the two-level test. You can nd further descriptions and explanations of two-level tests in [6, 7, 8, 9, 14, 15]. However, NIST recommends that the sample size at the second level should be on the order of the i…”
BackgroundPareschi, F., Rovatti, R., & Setti, G. (2012) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2012.2185227 · Cited by 189 · cited 2×
“efects of the DFT test. Indeed, NIST 12 Hiroshi Haramoto corrected the approximation of the variance to a better value ˙2 1 = 0:050:95n=4 proposed by Kim et al. [5] from ˙2 0 . Later, Pareschi et al. [15] found a further good approximation value ˙2 2 = 0:050:95n=3:8. According to [3], we use ˙2 2 for variance in the f…”
BackgroundMethodTesting random number generators
L'Ecuyer, P. (1992) · Proceedings of the 24th conference on Winter simulation - WSC '92 · doi:10.1145/167293.167354 · Cited by 115 · cited 1×
“Further descriptions and explanations of two-level tests can be found in [6, 7, 8, 9, 14, 15] However, NIST recommends that the sample size at the second level should be on the order of the inverse of the significance level, without any mathematical justifications.”
BackgroundCorrections of the NIST Statistical Test Suite for Randomness
Kim, S.-J., Umeno, K., & Hasegawa, A. (2004) · arXiv · doi:10.48550/arxiv.nlin/0401040 · Cited by 54
Research works printed but not linked: 1
- Yamaguchi, A., Saito, A.: On the statistical test of randomness based on the uniformity of $$p$$-values used in NIST statistical test suite. In: Proceedings of the 2015 JSIAM Annual Meeting, Applied Chaos, pp. 1–2 (2015)
Cited by
Second-level randomness test based on the Kolmogorov-Smirnov test
Yamaguchi, A., & Saito, A. (2022) · JSIAM Letters · doi:10.14495/jsiaml.14.73 · Cited by 5
Square Transposition Method with Adaptive Key Flexibility and Strong Diffusion Performance
Pakereng, M. A. I., Wowor, A. D., Beeh, Y. R., David, F., Christianto, E., Susanto, V. E., & Canavaro, C. (2025) · Matrik Jurnal Manajemen Teknik Informatika dan Rekayasa Komputer · doi:10.30812/matrik.v24i3.5004
Research on Software Optimization for Discrete Fourier Test
Yang, X., & Wang, L. (2025) · Axioms · doi:10.3390/axioms15010004
“…instance, Li et al. [10] designed a jump test based on jump complexity to calculate the sum of jump heights across intervals; Haramoto [11] proposed upper bounds for sample sizes in secondary tests corresponding to six items in NIST SP 800-22; Abdelwahab et al. [12] analyzed the…”
SIMD-Accelerated Optimization of Runs Test Performance on Binary Sequences
Kang, H., Guo, B., Luo, Y., & Shi, N. (2026) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001426500011
Park, H.-J., Ngo, C. T., Lee, M.-H., & Hong, J.-P. (2026) · IEEE Access · doi:10.1109/access.2026.3667853 · Cited by 1
“That is, it may judge a statistically random bitstream as non-random even when the underlying RNG output is truly random [7], [8], [9], [10].”
Metadata
- Authors
- Haramoto, H.
- Affiliations
- Ehime University (JP)
- Corresponding author
- Haramoto, Hiroshi
- ORCID
- Haramoto, Hiroshi
- Venue
- Japan Journal of Industrial and Applied Mathematics
- Published
- 2020-07-22
- Volume
- 38
- Issue
- 1
- Pages
- 193-209
- ISSN
- 0916-7005 (ISSN-L)
- 1868-937X
- OpenAlex
- W3044307745
- Semantic Scholar
- 73570dd75b844f9938c18a2a7deb06665f8ed328
- Cited by
- 5
- References
- 19
- Citations by year
- 2026: 2 · 2025: 2 · 2022: 1
- FWCI
- 0.18
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.springer.com/tdm (tdm)
- www.springer.com/tdm (vor)
- Locations
- Japan Journal of Industrial and Applied Mathematics (publishedVersion)
- Funders
- Japan Society for the Promotion of Science (JSPS KAKENHI Grant Number, 17K14234, JSPS KAKENHI Grant Number, 16K13750, JSPS KAKENHI Grant Number, 18K03213)
- Topics
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptographic Implementations and Security
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Coding theory and cryptography
- Keywords
- pseudorandom number generators, p-value distribution, chi-squared goodness of fit, statistical randomness testing
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Study on upper limit of sample size for a two-level test in NIST SP800-22. https://app.cochat.ai/papers/10.1007/s13160-020-00434-y
- The paper
- Haramoto, H. (2021). Study on upper limit of sample size for a two-level test in NIST SP800-22. Japan Journal of Industrial and Applied Mathematics. https://doi.org/10.1007/s13160-020-00434-y
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.