0
$\begingroup$

If I test the Pseudo Random Number Generator(PRNG) and it satisfies the serial test, it is not sure that the resulting distribution is uniform. Is my observation correct? If it is correct, what test should I do to be sure?

$\endgroup$
5
  • $\begingroup$ [not an answer!] I guess you consider this serial test. Are you looking for the monobit test? That tests uniformity, but not independence of the bits. Nothing can reliably test the later. $\endgroup$
    – fgrieu
    Jan 18, 2023 at 9:07
  • $\begingroup$ I'm trying to understand mainly if the PRNG passes the serial test then it is not uniform distribution and why? $\endgroup$ Jan 18, 2023 at 10:10
  • $\begingroup$ @fgrieu Standard permutation testing can identify independence :-) $\endgroup$
    – Paul Uszak
    Jan 18, 2023 at 13:03
  • $\begingroup$ @Paul Uszak: consider the PRNG based on a 64-byte hash $H$ (e.g. SHA-512) and 32-byte constant $C$, that given 32-byte seed $S$ first outputs 64-byte $R_0=H(C\mathbin∥S)$, then 64-byte $R_{i+1}=H(C\mathbin∥R_i)$. New output $R_{i+1}$ is dependent on $R_i$, and nothing else variable. Yet no test will identify that, or otherwise distinguish from random the outputs of the PRNG for different seeds, unless the test somehow knows $C$. Testing can sometime identify dependence. Does that mean "testing can identify independence"? You decide on that semantic issue. $\endgroup$
    – fgrieu
    Jan 18, 2023 at 13:44
  • $\begingroup$ @fgrieu Oh I see! I thought that you were referring to the output sequence since we're talking about tests on that... $\endgroup$
    – Paul Uszak
    Jan 18, 2023 at 14:31

1 Answer 1

1
$\begingroup$

I assume the question is about this serial test.

If I test a Pseudo Random Number Generator (PRNG) and it satisfies the serial test, it is not sure that the resulting distribution is uniform.

Yes. No test on the output of a PRNG is able to make one sure of anything about the distribution of the output of the PRNG, for the mathematical definition of sure. Argument: it's possible that the PRNG outputs 0 starting at the $2^{160}$-th bit that it outputs, and it's trivial to make such PRNG that passes all practical tests ever devised. I admit this argument of correctness of the quoted proposition is not helpful.

For something more helpful, we must reach some functional interpretation of "sure that the resulting distribution is uniform". For a start, we should decide if this shall hold for a PRNG which computes it's first output bit from the seed, then always outputs the complement of the previous output bit (so that it's output is either 0101010101… or 1010101010… depending on the seed).

  1. If we accept that for such pathological PRNG "the resulting distribution is uniform" can hold (perhaps, according to how the first bit is computed), then we are interested only in the frequency of bits in the output. The best possible test on the output of a PRNG for the property that we want is the monobit test.
  2. Otherwise, our interpretation of "sure that the resulting distribution is uniform" likely is that we want assurance that the output bits of the PRNG are indistinguishable form a uniform distribution of independent bits.

For both meanings, the quoted proposition is true if parameter $m\ge2$ in the serial test. That parameter defines the length of the bit subsequences which frequency is assessed. Argument: it's possible to construct a PRNG which output sequences for a given (nontrivial) length both reliably pass the serial test, but reliably fail the monobit test. The idea is that the subsequences of $m$ bits have a distribution within the tolerance of the serial test, but overall the bias of individual bits is above the threshold of the monobit test.

For $m=1$ the serial test aims at being equivalent to the monobit test, and I think it is; that would arguably make the proposition false for meaning 1 and $m=1$.

For meaning 2, the proposition is true because it's impossible to experimentally reach the desired conclusion by any test on the output of a PRNG, even if we accept a high residual probability of falsely reaching that conclusion (say, 25%). Argument: even if many PRNG tests succeed, it's always possible that the output sequence(s) of the PRNG have some regularity that escape these tests, but is caught by a test tailored to the internals of the PRNG. The best a PRNG test can do is disprove, within an extremely small residual probability of the contrary (say, 0.01%), that "the resulting distribution is uniform" for meaning 2; and that can occur only when the test fails.

What test should I do to be sure?

Again, for meaning 1, the monobit test is the best there is. And even if that passes, you can't be sure.

For meaning 2, no test on the output of a PRNG can give a meaningful assurance (much less certainty) "that the resulting distribution is uniform". Only examining the construction of the PRNG can give such assurance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.