Читать «Компьютерра PDA N71 (06.11.2010-13.11.2010)» онлайн - страница 7

Конструирование физических датчиков основано на том, что двоичное представление стандартного случайного числа α (а именно такое представление чисел реализуется в компьютере) имеет вид

α = 0,10011001010...

то есть целая часть числа равна нулю (ведь α расположено между нулем и единицей), а в "хвосте", следующем после запятой (этот "хвост" по научному называется мантиссой, а нули и единицы заполняют разряды мантиссы), стоят нули и единицы. Появление нуля и единицы (вне зависимости от значений в соседних разрядах) происходит с равной вероятностью (то есть с вероятностью 1/2).

Далее нужно сконструировать тот самый "шумящий" прибор, выдающий или не выдающий случайный сигнал в данный момент времени. Получение стандартных чисел α_j сведется к формированию соответствующих "хвостов" (мантисс) с помощью многократного обращения к прибору (наличие сигнала даст единицу в разряде мантиссы, отсутствие его даст нуль).

Определенная сложность состоит в том, что для применения методов Монте-Карло требуется прибор, позволяющий получать нули и единицы в разрядах мантиссы с равной вероятностью.

К слову, при получении чисел (шифров) в криптографии последнее требование желательно, но не обязательно. Здесь нет нужды увязывать наборы нулей и единиц с приведенным выше представлением стандартного числа α_j. Если обнаруживаются слишком длинные серии нулей или единиц, то реализуются специальные алгоритмы, удаляющие следы повторяемости. Это тоже обуславливает существенное отличие "криптографических" чисел от стандартных случайных чисел, используемых в методах Монте-Карло: для последних длинные серии нулей и единиц в мантиссе вполне допустимы.

- Какие сигналы можно использовать в физических датчиках?

- Можно крутить рулетку, раскрасив предварительно круг в два цвета (например, в красный и черный); красный цвет может соответствовать единице, черный - нулю. К слову, этот возможный способ получения стандартных случайных чисел обусловил название методов Монте-Карло, ведь в знаменитом игорном центре тоже крутят рулетку. Недостаток этого способа получения случайных чисел: долгое время реализации и отсутствие автоматизации процесса получения случайных нулей и единиц. Зато здесь более-менее гарантирована вероятность 1/2, если круг раскрашен двумя цветами пополам.

Автоматизация процесса формирования мантиссы стандартного случайного числа связана с применением различных случайных шумов. Иногда используются шумы самого компьютера. Более надежными и быстрыми считаются квантовые генераторы случайных шумов, в которых используются специальные свойства потоков малых (элементарных) частиц.

Проблему получения равных вероятностей появления нуля и единицы часто решают следующим образом. Сигнал замеряют дважды. Возможны следующие исходы: оба раза сигнал был (состояние СС), оба раза сигнала не было (состояние НН), первый был - второго не было (состояние СН) и первый не был - второй был (состояние НС). Если даже вероятность появления сигнала не равнялась в точности 1/2, то все равно состояния НС и СН являются равновероятными. То есть можно фиксировать только эти два состояния (приписав, например, состоянию НС единицу, а СН - нуль), а состояния СС и НН игнорировать.