Adaptive $\chi^2$ Criterion for Discrimination of Near Hypotheses with a Large Number of Classes and Its Application to Some Cryptography Problems

The main problem considered consists in testing the hypothesis $H_0$ that letters of an alphabet $A=\{a_1,a_2,\dots,a_k\}$ are generated with equal probabilities $\frac{1}{k}$ against the alternative complex hypothesis $H_1$, the negation of $H_0$. In many applications, in particular, those connected with cryptography, $k$ is large, but possible deviations from the uniform distribution are small. Therefore, application of Pearson's $\chi_2$ test, which is one of the most wide-spread and efficient tests, requires samples of a very large size, certainly exceeding $k$. We propose a so-called adaptive $\chi_2$ test, whose power can be considerably higher than that of the traditional method in the case described. This conclusion is based on the theoretical analysis of the proposed criterion for some classes of alternatives as well as on experimental results related to discriminating between enciphered Russian texts and random sequences.