Adaptive Chi-Square Test and its Application to Some Cryptographic Problems
Boris Ya. Ryabko, V.S. Stognienko, Yu. I. Shokin · 2002
We address the problem of testing the hypothesis H 0 that the letters from some alphabet A = {a 1 , a 2 , . . . , a k }, are distributed uniformly (i.e. p(a 1 ) = p(a 2 ) = . . . = p(a k ) = 1/k) against the alternative hypothesis H 1 that the true distribution is not uniform, in case k is large. (It is typical for random number testing and some cryptographic problems where k = 2 10 # 2 30 and more, see [2, 8, 6]). In such a case it is di#cult to use the chi-square test because the sample size must be greater than k.