CoChat
Sign Up
Cited by 8Mathematical Approximation and IntegrationProbability and Statistical ResearchSimulation Techniques and Applications

Checking the quality of approximation of p-values in statistical tests for random number generators by using a three-level test

Open access
Haramoto, Hiroshi, Matsumoto, Makoto·2019·Mathematics and Computers in Simulation
DOI 10.1016/j.matcom.2018.08.005
Open this paper in CoChat — free account

Abstract

Abstract Statistical tests of pseudorandom number generators (PRNGs) are applicable to any type of random number generators and are indispensable for evaluation. While several practical packages for statistical tests of randomness exist, they may suffer from a lack of reliability: for some tests, the amount of approximation error can be deemed significant. Reducing this error by finding a better approximation is necessary, but it generally requires an enormous amount of effort. In this paper, we introduce an experimental method for revealing defects in statistical tests by using a three-level test proposed by Okutomi and Nakamura. In particular, we investigate the NIST test suite and the test batteries in TestU01, which are widely used statistical packages. Furthermore, we show the efficiency of several modifications for some tests.

AI snapshot

Written from the paper’s full text.

TL;DR

The paper introduces a three-level test, based on Okutomi and Nakamura’s method, to check whether the approximation used for \(p\)-values in statistical tests for PRNGs is adequate. Applying it to the NIST test suite and TestU01’s SmallCrush and Crush batteries reveals flawed approximations in several tests and supports several modifications and parameter changes.

Key findings

  • In the NIST suite, the original three-level test gave very small \(p\)-values for the Discrete Fourier Transform test (\(4.1\mathrm{E}{-119}\) for MT, \(7.2\mathrm{E}{-116}\) for SHA1), Overlapping Template Matching (\(7.5\mathrm{E}{-80}\), \(5.6\mathrm{E}{-73}\)), Maurer’s Universal Statistical test (\(8.7\mathrm{E}{-76}\), \(4.1\mathrm{E}{-66}\)), and Longest Run of Ones in a Block (\(3.9\mathrm{E}{-5}\), \(1.3\mathrm{E}{-8}\)); after modifications, these became reasonable, e.g. DFT \(0.19/0.026\), Overlapping \(0.70/0.88\), Maurer \(0.99/0.77\), Longest Run \(0.44/0.0011\).
  • For the NIST Random Excursions test, \(x=4\) showed flaws up to \(J=1500\); the authors recommend \(J \ge 2000\) instead of NIST’s \(J \ge 500\), with first-level sample size \(n=10^7\). For the Random Excursions Variant test, too-small \(p\)-values for \(x=\pm 9\) led them to recommend \(J \ge 1000\).
  • In TestU01 SmallCrush, the 14 assessed test statistics had sufficiently accurate \(p\)-value approximations. In Crush, tests rejected by both MT and SHA1 included `svaria_SampleCorr`, `smarsa_Savir2`, `scomp_LempelZiv`, `sspectral_Fourier3`, and `sstring_Run`; modifications improved `svaria_SampleCorr` from \(1.8\mathrm{E}{-222}/5.5\mathrm{E}{-237}\) to \(0.498/0.825\), and `sstring_Run` from \(\varepsilon\) to \(0.657/0.302\) and \(0.715/0.0479\).
  • `smarsa_Savir2` remained unresolved; the authors tentatively propose \(t=9\) as a compromise. `scomp_LempelZiv` and `sspectral_Fourier3` still needed more mathematical justification, with `sspectral_Fourier3` yielding \(p\)-values below \(10^{-300}\).

Methods

  • The three-level test uses an error-free second level: first-level statistics \(f(a_i)\) are computed; second-level counts \(T_i\) of first-level \(p\)-values \(\ge \alpha\) in blocks; third-level compares \(T_1,\dots,T_{N'}\) to the binomial distribution \(B(N,1-\alpha)\) via a \(\chi^2\) goodness-of-fit test with 16 degrees of freedom. Parameters follow Okutomi and Nakamura: \(\alpha=0.01\), \(N=10^3\), \(N'=10^3\).
  • Experiments use Mersenne Twister and a SHA1-based PRNG to mimic random sequences. NIST tests use first-level sample size \(n=10^6\), except Random Excursions tests use \(n=10^7\). For Crush, MT is applied first; if the three-level \(p\)-value is below \(10^{-10}\), SHA1 is also used, and the test is rejected only if both are below \(10^{-10}\).
  • Modifications tested include DFT parameter \(d=3.8\), removing lines 40–44 in `overlappingTemplateMatching.c`, using Coron’s variant for Maurer’s Universal test, more accurate Longest Run probabilities to 15 decimal places, centering the `svaria_SampleCorr` statistic, and correcting the `sstring_Run` normal and \(\chi^2\) statistics.

Limitations

  • The paper states that the method assumes the approximated statistic distribution is continuous, because it relies on uniformity of first-level \(p\)-values in \([0,1]\); this is not essential if the exact \(p\)-value distribution can be computed. It also notes that the Random Excursions tests discard samples, so the three-level formalism does not apply as-is, and the authors iterate first-level tests until \(N=1000\) \(p\)-values are obtained.
  • The authors state they could not give satisfactory mathematical modifications for `smarsa_Savir2`, `scomp_LempelZiv`, or `sspectral_Fourier3`; for `smarsa_Savir2` they only tentatively propose \(t=9\). They also suggest a Kolmogorov–Smirnov test may be more appropriate and powerful than the \(\chi^2\) GOF test at the third level.
  • Evident from the text: the Crush screening procedure only checks SHA1 when the MT three-level \(p\)-value is below \(10^{-10}\), so tests with moderate approximation error may not be rechecked; and the conclusions depend on the two chosen generators, MT and SHA1, with MT noted to fail certain tests even when \(p\)-values are computed correctly.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1016/j.matcom.2018.08.005

Cites

25 of 25 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

6 of 21 cited sources checked · 2 supported · 0 flagged · accuracy not yet measured

  • Premisenone given
    § 4. Experimental results · p. 5

    MT fails certain tests, e.g., the linear complexity test and the binary matrix rank test with large matrix size, even when the p-value is computed correctly with no significant error.

    “Note that MT fails certain tests (e.g. the linear complexity test, the binary matrix rank test with large matrix size) even when the p -value is computed correctly with no significant error.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [15] Matsumoto, 1998, Mersenne Ttister: A 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans. Model. Comput. Simul. source

      Section 1.4 reports that MT19937 passed the Diehard and other empirical tests, while §3.1 describes MT as an F₂-linear generator. Our copy does not report failures of the linear complexity test or a large-matrix binary rank test, or discuss whether correctly computed p-values affect those results (searched: linear complexity, binary matrix rank, p-value, statistical test failures). (LLM, conf=0.75)

      Experimental — accuracy not yet measured
  • Premisecitation
    § 4.1. Results of the NIST test suite · p. 6

    The latest version 2.1.2 of the NIST test suite, released in 2014, does not incorporate several modifications.

    “However, the latest version 2.1.2 [1], released in 2014, does not incorporate several modifications.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [1] Bassham, 2010 source

      Section 2, “Random Number Generation Tests,” identifies and describes the NIST Test Suite. Our copy does not establish that version 2.1.2 was the latest release in 2014 or that it omitted several modifications; searches for the version, release date, and modifications found no supporting passage. (LLM, conf=0.78)

      Experimental — accuracy not yet measured
  • Findingown data
    § 4.1. Results of the NIST test suite · p. 6

    In the original NIST test suite, the three-level test p-values for the Discrete Fourier Transform test are much too small.

    “From our experiments, the p -values from the Discrete Fourier Transform (DFT) test, the Overlapping Template Matching test, and the Maurer's Universal Statistical test in the original test suite are much too small.”
    Quote in the paperSubstantial claim
  • Findingnone given
    § 4.2. Results for SmallCrush and Crush in TestU01 · p. 15

    The resulting p-values of the scomp_LempelZiv and sspectral_Fourier3 tests are smaller than 10^-300.

    “Indeed, the resulting p -values of those tests are smaller than 10 -300 , so more mathematical justifications for those tests are needed.”
    Quote in the paperSubstantial claim
  • Findingown data
    § 4.1. Results of the NIST test suite · p. 10

    For the Random Excursions Variant test, the p-values for x = ±9 are too small.

    “For the Random Excursions Variant test, from the too small p -values for x = ± 9, we recommend a constraint J ≥ 1000.”
    Quote in the paperSubstantial claim
  • May combine two claims. 11
  • Classified as probably not a substantial claim. 10
  • The quote only partly states this claim. 4

  • May combine two claims.

    Interpretationcitation
    § 2. Statistical testing for PRNGs and approximation error · p. 3

    In two-level tests, computational errors accumulate at each level and two-level tests detect the lack-of-fit of the approximation, leading to rejection even if the generator is good.

    “In this case, computational errors accumulate at each level and two-level tests detect the Lack-Of-Fit of that approximation, leading to rejection even if the generator is good [7, 10, 13, 17].”
    Quote in the paperSubstantial claim1 of 4 sources checked
    • cites [7] L’Ecuyer, 1992, Testing random number generators source
    • cites [10] L’Ecuyer, 2000, Close-point spatial tests and their application to random number generators, Oper. Res. source
    • cites [13] L’Ecuyer, 2002, Sparse serial tests of uniformity for random number generators, SIAM J. Sci. Comput. source
    • cites [17] Pareschi, 2012, On statistical tests for randomness included in the NIST SP800-22 test suite and based on the binomial distribution, IEEE Trans. Inf. Forensics Secur. source

      The 'C. Reliability of a Two-level Test' section says approximation errors in basic-test p-values make their distribution deviate from the expected uniform distribution, and that the resulting second-level error grows with the number of sequences. It also reports that two-level tests can fail for very large samples despite using a high-quality generator. The paper does not say computational errors arise and accumulate at each level; it traces the problem to the basic-test approximation and its effect on the second-level test. Page numbers are unavailable in our copy. (LLM, conf=0.82)

      Experimental — accuracy not yet measured
    • The authors state this as an assumption: In this manuscript, H0 is assumed, i.e., the tested PRNGs are good.

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Premisecitation
    § 4.1. Results of the NIST test suite · p. 6

    The NIST test suite consists of 15 statistical tests for randomness of bit sequences, and its result is a list of 188 p-values.

    “The NIST test suite consists of 15 statistical tests for randomness of bit sequences, and its result is a list of 188 p -values.”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites [1] Bassham, 2010 source

      Section 2, “Random Number Generation Tests,” confirms that the suite has 15 tests for randomness in binary sequences. The claim that its result is a list of 188 p-values is not supported: Section 4.4 describes 161 tests producing significance probabilities, while Section 2.7.4 says the number of p-values from one test varies with its parameters. (LLM, conf=0.88)

      Experimental — accuracy not yet measured

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 4.1. Results of the NIST test suite · p. 8

    Pareschi et al. proposed d=3.8 for n≈10^6 for the DFT test.

    “Subsequently, Pareschi et al. [17] proposed d = 3 . 8 for n ≈ 10 6 , which we use here as modification.”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites [17] Pareschi, 2012, On statistical tests for randomness included in the NIST SP800-22 test suite and based on the binomial distribution, IEEE Trans. Inf. Forensics Secur. source

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 4.1. Results of the NIST test suite · p. 6

    The current implementation of the NIST test suite uses one-level or two-level tests, differently from the above experiments.

    “Note that the current implementation of the NIST test suite uses one-level or two-level tests, differently from the above experiments”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites [1] Bassham, 2010 source

  • The quote only partly states this claim.

    Findingown data
    § 4.2. Results for SmallCrush and Crush in TestU01 · p. 14

    The modifications to svaria_SampleCorr and sstring_Run are satisfactory in improving the reliability of the tests.

    “The results indicate that the above modifications are satisfactory in improving the reliability of the tests.”
    Quote in the paperSubstantial claim

  • The quote only partly states this claim.

    Findingown data
    § 4.1. Results of the NIST test suite · p. 6

    In the original NIST test suite, the three-level test p-values for the Longest Runs of Ones in a Block test are relatively small.

    “Additionally, the p -values of the Longest Runs of Ones in a Block test are relatively small.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Findingnone given
    § 4.1. Results of the NIST test suite · p. 8

    The C-code overlappingTemplateMatching.c changes the new values to the former wrong ones.

    “However, the C-code overlappingTemplateMatching.c changes the new values to the former wrong ones.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 4.2. Results for SmallCrush and Crush in TestU01 · p. 15

    The p-values of the smarsa_Savir2 test are slightly suspicious but not too small.

    “The p -values are slightly suspicious but not too small.”
    Quote in the paperSubstantial claim

  • The quote only partly states this claim.

    Findingown data
    § 4.2. Results for SmallCrush and Crush in TestU01 · p. 11

    In Crush, the tests rejected by both Mersenne Twister and SHA1 are svaria_SampleCorr, smarsa_Savir2, scomp_LempelZiv, sspectral_Fourier3, and sstring_Run.

    “Table 7 shows the tests rejected by both Mersenne Twister and SHA1.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationnone given
    § 3. Checking the quality of the approximation of the p -value by using a three-level test · p. 4

    Extending a statistical test from two to three or higher using a technique such as the one shown is often useless, because the approximation error of the second level may destroy the result: the resulting p-values tend to be too close to 0.

    “this type of test is often useless, because the approximation error of the second level may destroy the result: the resulting p -values tend to be too close to 0.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning
    § 3. Checking the quality of the approximation of the p -value by using a three-level test · p. 4

    Okutomi and Nakamura's three-level test allows increasing the sample size by N' times, and consequently increasing the power while avoiding an accumulation of computational errors.

    “This allows us to increase the sample size by N ′ times, and consequently to increase the power while avoiding an accumulation of computational errors.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [16] Okutomi, 2010, A study on rational judgement method of randomness property using NIST randomnes test (in Japanese), Trans. Inst. Electron. Inf. Commun. Eng. A

      Not checked in the free run.

  • May combine two claims.

    Interpretationnone given
    § 3. Checking the quality of the approximation of the p -value by using a three-level test · p. 5

    The presented method counts only the number of p-values at the second level, which has no approximation error introduced at this level under H0 and H'.

    “On the other hand, the presented method counts only the number of p -values at the second level, which has no approximation error introduced at this level (under the hypotheses H 0 and H ′ ).”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: In a statistical test, the distribution of f(X) under H0 is well-approximated by a known cumulative distribution F.
    • The authors state this as an assumption: In this manuscript, H0 is assumed, i.e., the tested PRNGs are good.

  • May combine two claims. The quote only partly states this claim.

    Interpretationreasoning
    § 3. Checking the quality of the approximation of the p -value by using a three-level test · p. 5

    A three-level test that uses a GOF test on the entire distribution of N' p-values under the uniform hypothesis will detect approximation error at the second level and tends to give p-values nearly zero if the distribution of the test statistic at the second level is only approximated and the approximation error is significant.

    “However, if the distribution of the test statistic at the second level is only approximated and the approximation error is significant, a three-level test will detect this approximation error, and tends to give p -values nearly zero.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationreasoning
    § 3. Checking the quality of the approximation of the p -value by using a three-level test · p. 5

    In the paper's purpose, using good PRNGs so H0 is assumed, a rejection at the third level is interpreted as H' being rejected, i.e., the approximation of f(X) by F is not good enough.

    “In our purpose, we use good PRNGs so that H 0 is assumed, and consider that H ′ is rejected, or equivalently the approximation of f ( X ) by F is not good enough.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: In this manuscript, H0 is assumed, i.e., the tested PRNGs are good.

  • May combine two claims.

    Interpretationnone given
    § 4.1. Results of the NIST test suite · p. 10

    For both the Random Excursions test and the Random Excursions Variant test, the first-level procedure yields a sequence of p-values that are uniform i.i.d. in [0,1] under the hypotheses H0 and H'.

    “However, for the both tests, the first level procedure yields a sequence of p -values which are uniform i.i.d in [0 , 1] under the hypotheses H 0 and H ′ .”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Interpretationnone given
    § 1. Introduction · p. 2

    The criterion only makes use of the uniformity of p-values, meaning that a wide range of tests can be subjected to the three-level method.

    “Furthermore, our criterion only makes use of the uniformity of p -values, meaning that a wide range of tests can be subjected to the three-level method.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationown data
    § 4.1. Results of the NIST test suite · p. 6

    The Discrete Fourier Transform, Overlapping Template Matching, Maurer's Universal Statistical, and Longest Runs of Ones in a Block tests have some flaws.

    “This result indicates that those tests have some flaws.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based). May combine two claims.

    Interpretationcitation
    § 5. Concluding remarks · p. 16

    A Kolmogorov-Smirnov (KS) test seems to be more appropriate and more powerful than a χ2 GOF test at the third level.

    “However, a Kolmogorov-Smirnov (KS) test seems to be more appropriate and more powerful.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 4.1. Results of the NIST test suite · p. 8

    The latest version of the NIST test suite uses the parameter d=4 proposed by Kim et al. for the DFT test.

    “The latest version of the NIST test suite uses the parameter d = 4 proposed by Kim et al. [5].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [5] Kim, 2004, Corrections of the NIST Statistical Test Suite for Randomness, IACR Cryptology EPrint Archive

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S2 (checkable), S3 (load-bearing).

    Interpretationown data
    § 4.2. Results for SmallCrush and Crush in TestU01 · p. 15

    More mathematical justifications for the scomp_LempelZiv and sspectral_Fourier3 tests are needed.

    “Indeed, the resulting p -values of those tests are smaller than 10 -300 , so more mathematical justifications for those tests are needed.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Premisecitation
    § 5. Concluding remarks · p. 16

    An accurate approximation of the KS distribution is now available [18].

    “An accurate approximation of the KS distribution is now available [18]”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [18] Simard, 2011, Computing the two-sided Kolmogorov-Smirnov distribution, J. Statist. Softw. Articles source
21 of 21

  • The authors state this as an assumption.

    In a statistical test, the distribution of f(X) under H0 is well-approximated by a known cumulative distribution F.

    “In a statistical test, we assume that the distribution of f ( X ) under H 0 is well-approximated by a known (cumulative) distribution F .”

  • The authors state this as an assumption.

    In this manuscript, H0 is assumed, i.e., the tested PRNGs are good.

    “In this manuscript, H 0 is assumed and hence the precision of the approximation ( H ′ ) is rejected.”

  • The authors state this as an assumption.

    The approximating distribution F in the hypothesis H' is continuous.

    “Here we make an assumption: the approximating distribution F in the hypothesis H ′ is assumed to be continuous.”

  • The authors state this as an assumption.

    H' includes the assumption that each probability mass is small enough to be negligible by itself.

    “Thus, H ′ includes the assumption that each probability mass is small enough to be negligible by itself.”

  • The authors state this as an assumption.

    The approximated statistics are continuous.

    “In this study, we need to assume that the approximated statistics are continuous, because our three-level test is based on the uniformity of p -values in [0 , 1] at the first level.”
5 of 5

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • Third-level probabilities use a different binomial model

    Minor

    The text says the counts follow B(N, 1−α), with α = 0.01. But the stated formula for p_i divides binomial coefficients by 2^N, which gives probabilities for B(N, 1/2), not the stated distribution.

1 of 1

Cites

Flagged first, then by citations

1 of the 26 references couldn’t be matched to a known paper.

Research works printed but not linked: 1

  1. Okutomi, 2010, A study on rational judgement method of randomness property using NIST randomnes test (in Japanese), Trans. Inst. Electron. Inf. Commun. Eng. A, 93, 11

Cited by

Sorted by citations

Related

Authors
Haramoto, H., & Matsumoto, M.
Affiliations
  • Ehime University (JP)
  • Hiroshima University (JP)
Corresponding author
Haramoto, Hiroshi
ORCID
Venue
Mathematics and Computers in Simulation
Publisher
Elsevier BV
Published
2019-07
Volume
161
Pages
66-75
ISSN
0378-4754 (ISSN-L)
DOI
10.1016/j.matcom.2018.08.005
OpenAlex
W2886864997
Semantic Scholar
991edba7af434cf7bc2d313e2e842c3b67e72e56
Cited by
8
References
26
Citations by year
2026: 1 · 2024: 1 · 2021: 1 · 2020: 3 · 2019: 2
FWCI
1.41
Type
journal article
Language
en
Open access
Licence
Locations
  • Mathematics and Computers in Simulation (acceptedVersion)
  • arXiv (Cornell University) (submittedVersion)
Funders
  • JSPS KAKENHI (26310211, 15K13460, 16K13750, 17K14234, 18K03213)
  • JST CREST
Topics
  • Physical Sciences › Mathematics › Numerical Analysis › Mathematical Approximation and Integration
  • Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Simulation Techniques and Applications
Keywords
pseudorandom number generators, randomness testing, p-value approximation, approximation error, NIST SP 800-22, TestU01, test reliability

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.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-09.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-09.

Cited sources are checked by gpt-6-sol.

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