Linear Complexity Profile as a Means of Measuring the Quality of Random Sequences

摘要

Linear complexity and its properties are an important measure of the quality of random sequences. The NIST statistical test package contains a linear complexity test, however it stops recognizing the linear recurrent sequences even at their smallest distortions. The new tests, based on the properties of linear complexity profile, appear to be more effective while searching for linear dependencies between the elements of a sequence. The following statistical tests are described and experimentally compared in the article: the NIST test, Hamano-Sato-Yamamoto test, and LP-test, which has been proposed by the authors.