NIST removed "The Lempel-Ziv Compression" test from the Statistical Test Suite in revision 2008 and above and has not incorporated it since – see revision 2010.

Why was it removed? Does it no longer provide sufficient testing of a PRNG or was it simply superseded by better tests?


1 Answer 1


According to the paper On Lempel-Ziv Complexity of Sequences by Doganaksoy and Gologlu,

A test based on Lempel-Ziv complexity was used in the NIST test suite, to test the randomness of sequences. However the test had some weaknesses. First of all, the test could only be applied to data of a specified length: $10^6$ bits. Moreover, the test used empirical data generated by SHA-1 (under randomness assumptions) for estimating the expected value of Lempel-Ziv complexity of sequences of length $10^6$ bits. Apparently, the data generated by SHA-1 led to not-so-good an estimate, hence, for instance, first $10^6$ bits of the binary expansion of $e$ failed the randomness test. Using asymptotic formulae for an estimate will not work either, since the sequences, as we will see in the forthcoming sections, are distributed tightly around the mean. Recently, apparently because of the spelt out reasons, Lempel-Ziv test had been excluded from the NIST test suite.

The Crypt-XS package, part of the NIST suite, includes the simply named sequence complexity test, which is based on Lempel-Ziv compression.

  • 2
    $\begingroup$ Just to be clear, are you saying that the test was dropped because it's NIST implementation was poor, whilst theoretically the test is valid? Thus $e$ should pass the test if it were properly constructed? $\endgroup$
    – Paul Uszak
    Commented Feb 24, 2019 at 23:06

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.