- Антон Вацлавович, чем различаются случайные и псевдослучайные числа в теории методов Монте-Карло? Как они соотносятся с понятием случайного числа в криптографии?
- При применении методов численного статистического моделирования требуется получать на компьютере выборочные значения случайных величин с различными законами распределения. Здесь используются различные формульные и алгоритмические преобразования стандартных случайных чисел αj которые распределены равномерно в интервале (0,1) («на пальцах» это означает, что частота появления этих чисел в различных частях единичного интервала одинакова). А вот для получения чисел αj используются датчики (генераторы) стандартных случайных чисел.
Различают физические датчики случайных чисел (основанные, кстати, на использовании упомянутых выше «шумящих» приборов) и генераторы псевдослучайных чисел (это специальные компьютерные программы, имеющие в языках программирования названия RAND или RANDOM).
Конструирование физических датчиков основано на том, что двоичное представление стандартного случайного числа α (а именно такое представление чисел реализуется в компьютере) имеет вид
α = 0,10011001010...
то есть целая часть числа равна нулю (ведь α расположено между нулем и единицей), а в «хвосте», следующем после запятой (этот «хвост» по научному называется мантиссой, а нули и единицы заполняют разряды мантиссы), стоят нули и единицы. Появление нуля и единицы (вне зависимости от значений в соседних разрядах) происходит с равной вероятностью (то есть с вероятностью 1/2).
Далее нужно сконструировать тот самый «шумящий» прибор, выдающий или не выдающий случайный сигнал в данный момент времени. Получение стандартных чисел αj сведется к формированию соответствующих «хвостов» (мантисс) с помощью многократного обращения к прибору (наличие сигнала даст единицу в разряде мантиссы, отсутствие его даст нуль).
Определенная сложность состоит в том, что для применения методов Монте-Карло требуется прибор, позволяющий получать нули и единицы в разрядах мантиссы с равной вероятностью.
К слову, при получении чисел (шифров) в криптографии последнее требование желательно, но не обязательно. Здесь нет нужды увязывать наборы нулей и единиц с приведенным выше представлением стандартного числа αj. Если обнаруживаются слишком длинные серии нулей или единиц, то реализуются специальные алгоритмы, удаляющие следы повторяемости. Это тоже обуславливает существенное отличие «криптографических» чисел от стандартных случайных чисел, используемых в методах Монте-Карло: для последних длинные серии нулей и единиц в мантиссе вполне допустимы.
- Какие сигналы можно использовать в физических датчиках?
- Можно крутить рулетку, раскрасив предварительно круг в два цвета (например, в красный и черный); красный цвет может соответствовать единице, черный — нулю. К слову, этот возможный способ получения стандартных случайных чисел обусловил название методов Монте-Карло, ведь в знаменитом игорном центре тоже крутят рулетку. Недостаток этого способа получения случайных чисел: долгое время реализации и отсутствие автоматизации процесса получения случайных нулей и единиц. Зато здесь более-менее гарантирована вероятность 1/2, если круг раскрашен двумя цветами пополам.
Автоматизация процесса формирования мантиссы стандартного случайного числа связана с применением различных случайных шумов. Иногда используются шумы самого компьютера. Более надежными и быстрыми считаются квантовые генераторы случайных шумов, в которых используются специальные свойства потоков малых (элементарных) частиц.
Проблему получения равных вероятностей появления нуля и единицы часто решают следующим образом. Сигнал замеряют дважды. Возможны следующие исходы: оба раза сигнал был (состояние СС), оба раза сигнала не было (состояние НН), первый был — второго не было (состояние СН) и первый не был — второй был (состояние НС). Если даже вероятность появления сигнала не равнялась в точности 1/2, то все равно состояния НС и СН являются равновероятными. То есть можно фиксировать только эти два состояния (приписав, например, состоянию НС единицу, а СН — нуль), а состояния СС и НН игнорировать.
Есть много ученых и практиков, убежденных в том, что только физические датчики могут дать «настоящие», «поистине случайные» наборы нулей и единиц. Ирония ситуации состоит в том, что уверенность этих исследователей часто зиждется на незнании природы того или иного шума (а вдруг он возникает благодаря каким-то вполне детерминированным — неслучайным — процессам?!).