Ученый из НГУ создал асимптотически оптимальные тесты для генераторов случайных чисел

19 августа 2021

Наука

Вам может показаться, что случайные числа – это что-то далекое и неизвестное. Но на самом деле мы встречаем их каждый день. Самый простой пример генерирования случайных чисел в обыденной жизни – это подбрасывание монеты: «орел» – это ноль, «решка» – единица. Подобный эксперимент можно повторить несколько раз, чтобы получить последовательность из нулей и единиц.

Сейчас случайные числа используются в компьютерных играх, в системах защиты информации, в численных методах решения вычислительных задач. Важно отметить, что с системами защиты информации мы встречаемся практически каждый день, покупая через интернет билеты на самолет, заказывая домой пиццу и совершая массу других покупок и платежей через интернет. При проведении этих действий необходимо ввести номер банковской карты и важно, чтобы этот номер и вся информация на карте были зашифрованы, иначе нечестные люди могут получить доступ к чужим деньгам.

Для шифрования информации в системах защиты используют генераторы, которые основаны на различных физических эффектах. Например, широко используются квантовые генераторы для вычисления с высокой скоростью последовательностей случайных чисел. Как и любой прибор, генераторы, построенные на физических явлениях, необходимо периодически проверять с помощью специально разработанных статистических тестов. Генераторы случайных чисел и тесты для них играют важную роль в системах защиты информации, поэтому в России, США, Германии и многих других технологически развитых странах разработаны стандарты для генераторов и тестов, применение которых обязательно на территории этих стран. В силу большой важности генераторов и тестов для информационных технологий, их разработкой и исследованием    занимаются сотни исследователей во всем мире, которые публикуют многочисленные статьи и монографии. 

Профессор Факультета информационных технологий Борис Рябко описал тест для генератора случайных чисел и доказал, что он асимптотически оптимален. 

 – Асимптотически – значит, что объем выборки нулей и единиц увеличивается. Сейчас используются мегабайты и даже гигабайты случайных чисел, которые производятся в течение дня в системах защиты информации. Так что вполне разумно рассматривать асимптотическое поведение генератора, когда мы работаем с действительно большими последовательностями из нулей единиц, – поделился ученый и также отметил, что ранее подобные тесты не были известны. 

Принцип работы оптимального теста построен на результатах науки о «сжатии данных», внешне очень далекой от математической статистики. Методы «сжатия данных» развиваются в рамках теории информации и также находят самое широкое применение при пересылке информации, например, писем электронной почты, фильмов, просматриваемых в YouTube и т.д. При тестировании случайных чисел используются неискажающие методы сжатия данных, т.е. такие, когда закодированный («сжатый») файл может быть декодирован к исходному виду. 

Неформально, основная идея теста очень проста: если длинная последовательность из нулей и единиц может быть существенно сжата (скажем, на один-два байта), то она не случайна. Интересно, что такого рода внешне простые соображения стали основой глубокой математической теории, основанной в прошлом веке российским математиком А. Н. Колмогоровым для определения понятия «случайное».

– Для меня теория информации и, в частности, сжатие данных, были математическими направлениями, в которых я получил первые результаты еще в аспирантском возрасте, поэтому для меня было совершенно естественно применять их в математической статистике, – рассказал Борис Рябко.

Теги: Наука, Факультет информационных технологий