zbMATH — the first resource for mathematics

Using information theory approach to randomness testing. (English) Zbl 1062.62004
Summary: We address the problem of detecting deviations of binary sequences from randomness,which is very important for random number (RNG) and pseudorandom number generators (PRNG). Namely, we consider a null hypothesis \(H_0\) that a given bit sequence is generated by a Bernoulli source with equal probabilities of 0 and 1 and the alternative hypothesis \(H_1\) that the sequence is generated by a stationary and ergodic source which differs from the source under \(H_0\). We show that data compression methods can be used as a basis for such testing and describe two new tests for randomness, which are based on ideas of universal coding. Known statistical tests and suggested ones are applied for testing PRNGs. These experiments show that the power of the new tests is greater than that of many known algorithms.

62B10 Statistical aspects of information-theoretic topics
62G10 Nonparametric hypothesis testing
65C10 Random number generation in numerical analysis
94A29 Source coding
Full Text: DOI arXiv
[1] Aho, A.V.; Hopcroft, J.E.; Ulman, J.D., The design and analysis of computer algorithms, (1976), Addison-Wesley Reading, MA
[2] Bailey, D.H., 1976. Sequential schemes for classifying and predicting ergodic processes. Ph.D. Dissertation, Stanford University.
[3] Bently, J.L.; Sleator, D.D.; Tarjan, R.E.; Wei, V.K., A locally adaptive data compression scheme, Comm. ACM, 29, 320-330, (1986) · Zbl 0648.94007
[4] Billingsley, P., Ergodic theory and information, (1965), Wiley New York · Zbl 0141.16702
[5] Dudewicz, E.J.; Ralley, T.G., The handbook of random number generation and testing with TESTRAND computer code, () · Zbl 0478.65003
[6] Elias, P., Interval and recency rank source codingtwo on-line adaptive variable-length schemes, IEEE trans. inform. theory, 33, 1, 3-10, (1987) · Zbl 0628.94010
[7] Gallager, R.G., Information theory and reliable communication, (1968), Wiley New York · Zbl 0198.52201
[8] Kendall, M.G.; Stuart, A., ()
[9] Knuth, E.E., ()
[10] Kolchin, V.F., Sevast’yanov, B.A., Chistyakov, V.P., 1976. The Random Allocation. Nauka, Moscow.
[11] Kolmogorov, A.N., Three approaches to the quantitative definition of information, Problems inform. transmission, 1, 3-11, (1965) · Zbl 0271.94018
[12] L’Ecuyer, P., 1994. Uniform random numbers generation. Ann. Oper. Res.
[13] Li, M.; Vitanyi, P., An introduction to Kolmogorov complexity and its applications, (1997), Springer New York · Zbl 0866.68051
[14] Maurer, U., A universal statistical test for random bit generators, J. cryptol., 5, 2, 89-105, (1992) · Zbl 0790.94014
[15] Mezenes, A.; van Oorschot, P.; Vanstone, S., Handbook of applied cryptography, (1996), CRC Press Boca Raton, FL
[16] Moffat, A., An improved data structure for cumulative probability tables, Software pract. exper., 29, 7, 647-659, (1999)
[17] Rozanov, Yu.A., The random processes, (1971), Nauka Moscow · Zbl 0252.62049
[18] Rukhin, A., et al., 2001. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST Special Publication 800-22 (with revision dated May 15, 2001). http://csrc.nist.gov/rng/SP800-22b.pdf.
[19] Ryabko, B.Ya., Information compression by a book stack, Problems inform. transmission, 16, 4, 16-21, (1980) · Zbl 0447.94009
[20] Ryabko, B.Ya., Twice-universal coding, Problems inform. transmission, 3, 173-177, (1984) · Zbl 0565.94012
[21] Ryabko, B.Ya., A locally adaptive data compression scheme (letter), Comm. ACM, 30, 9, 792, (1987)
[22] Ryabko, B.; Rissanen, J., Fast adaptive arithmetic code for large alphabet sources with asymmetrical distributions, IEEE comm. lett., 7, 1, 33-35, (2003)
[23] Ryabko, B.Ya.; Stognienko, V.S.; Shokin, Yu.I., A new test for randomness and its application to some cryptographic problems, J. statist. plann. inference, 123, 365-376, (2004) · Zbl 1045.62039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.