Профиль линейной сложности как средство оценки качества случайных последовательностей

Abstract

Лінійна складність та її властивості є важливою мірою якості випадкових послідовностей. В набір статистичних тестів NIST входить тест на лінійну складність, який, щоправда, перестає розпізнавати лінійні рекурентні послідовності навіть при їх незначних спотвореннях. Нові тести, засновані на характеристиках профілю лінійної складності, показали себе значно ефективнішими при виявленні лінійної залежності між елементами послідовності. Наведено опис та результати експериментального порівняння існуючих наразі тестів на лінійну складність: тесту NIST, тесту Хамано, Сато, Ямамото та запропонованого авторами LP-тесту.

Linear complexity and its properties are an important measure of sequence randomness. NIST statistical test suite contains a linear complexity test, however it stops recognizing the linear recurrent sequences as soon as the smallest distortion is introduced to them. 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: NIST linear complexity test, Hamano-Sato-Yamamoto test, and the LP-test, which was proposed by the authors.