文档介绍：Journal of Statistical Planning and
Inference 133 (2005) 95–110
ate/jspi
Using information theory approach to
randomness testingଁ
. Ryabko∗, . Monarev
Department of Applied Mathematics & Cybernatics, Siberian State University of munication &
Computer Science, Kirov str. 86, Novosibirsk 630102, Russian Federation
Received 1 July 2003; accepted 20 February 2004
Available online 1 July 2004
Abstract
We address the problem of detecting deviations of binary sequence from randomness,which is very
important for random number (RNG) and pseudorandom number generators (PRNG). Namely, we
consider a null hypothesis H0 that a given bit sequence is generated by Bernoulli source with equal
probabilities of 0 and 1 and the alternative hypothesis H1 that the sequence is generated by a stationary
and ergodic source which differs from the source under H0. We show that pression 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.
Those experiments show that the power of the new tests is greater than of many known algorithms.
© 2004 Elsevier . All rights reserved.
MSC: 62B10; 62G10; 62M07; 62M10; 94A29
Keywords: Hypothesis testing; Randomness testing; Random number testing; Universal code; Information
Theory; Random number generator; Shannon entropy
1. Introduction
The randomness testing of random number and pseudorandom number generators is
used for many purposes including cryptographic, modeling and simulation applications
ଁ Supported by INTAS Grant No. 00-738 and Russian Foundation for Basic Research under Grant No. 03-01-
00495.
∗
Corresponding author. Tel.: +7-3832-284938; fax: +1-3832-668030.
E-mail address: ******@ (. Ryabko)
0378-3758/$ - see front matter © 2004 Elsevier . All rights reserved.
doi:.
96 . Ryabko, .