Построение статистических критериев проверки гипотезы о чистой случайности на базе предикторов

А.Л. Костевич; А.В. Шилкин

Построение статистических критериев проверки гипотезы о чистой случайности на базе предикторов

А.Л. Костевич¹, А.В. Шилкин²

научная статья Страницы: 29-35

¹ к.ф.-м.н., руководитель группы разработки программных средств криптографической защиты информации, ЗАО «Авест»
² к.ф.-м.н., зав. сектором компьютерной безопасности НИЛ прикладной информатики, НИИ прикладных проблем математики и информатики

Ключевые слова: универсальный критерий проверка гипотезы о чистой случайности тест сжатия Лемпеля-Зива

Аннотация

Предложен подход к построению статистических критериев проверки гипотезы о чистой случайности для бинарных последовательностей на базе универсальных предикторов, позволяющий находить аналитическое выражение для мощности критерия. Построен критерий на базе универсального предиктора Лемпеля-Зива и найдено выражение для мощности критерия в случае н.о.р. испытаний Бернулли. Проведено сравнение предлагаемого критерия с тестом сжатия Лемпеля-Зива из NIST SP800-22.

Для цитирования

Костевич А.Л., Шилкин А.В. Построение статистических критериев проверки гипотезы о чистой случайности на базе предикторов // Системы высокой доступности. 2013. № 3. С. 29–35.

Список источников

NIST Special Publication 800-22. A statistical test suite for random and pseudorandom number generators for cryptographic applications. 2001.
Maurer U. A universal statistical test for random bit generators // J. of Cryptology. 1992. V. 5. № 2.P. 89-105.
Ryabko B.Ya., Monarev V.A. Using information theory approach to randomness testing // J. of Statistical Planning and Inference. 2005. V. 133. № 1. P. 95-110.
Kostevich A.L., Shilkin A.V. On Approach to Randomness Testing on the base of the Universal Predictors // Proceedings of the 8th International Conference «Computer Data Analysis and Modeling: Complex Stochastic Data and Systems». 2007. V. 1. P. 256-259.
Suzuki J. Universal prediction and universal coding // Systems and Computers. 2003. V. 34. № 6. P. 1-11.
Feder M., Merhav N., Gutman M. Universal prediction of individual sequences // IEEE Trans. on Information Theory. 1992. V. 38.№4. P. 1258-1270.

[1] NIST Special Publication 800-22. A statistical test suite for random and pseudorandom number generators for cryptographic applications. 2001.

[2] Maurer U. A universal statistical test for random bit generators // J. of Cryptology. 1992. V. 5. № 2.P. 89-105.

[3] Ryabko B.Ya., Monarev V.A. Using information theory approach to randomness testing // J. of Statistical Planning and Inference. 2005. V. 133. № 1. P. 95-110.

[4] Kostevich A.L., Shilkin A.V. On Approach to Randomness Testing on the base of the Universal Predictors // Proceedings of the 8th International Conference «Computer Data Analysis and Modeling: Complex Stochastic Data and Systems». 2007. V. 1. P. 256-259.

[5] Suzuki J. Universal prediction and universal coding // Systems and Computers. 2003. V. 34. № 6. P. 1-11.

[6] Feder M., Merhav N., Gutman M. Universal prediction of individual sequences // IEEE Trans. on Information Theory. 1992. V. 38.№4. P. 1258-1270.