На что указывает параметр датчика случайных чисел. Россияне придумали «первый в мире» биологический генератор случайных чисел
Различают три принципиально различных способа получения чисел, используемых в качестве случайных: физический, табличный и алгоритмический.
Считается, что первая попытка создать физический датчик случайных чисел относится к 3500 году до н.э. и связана с настольной игрой сенет, древнеегипетским светским развлечением. Согласно современным реконструкциям правил игры для определения набранного каждым игроком количества очков и очередности ходов в этой игре использовались четыре плоские палочки, одна сторона которых была белой, другая - черной. Палочки бросали одновременно и в зависимости от выпавшей комбинации цветов определяли дополнительные возможности игроков. В начале XX в. последовательности случайных чисел имитировались вручную - с помощью бросаний монеты или игральной кости, раскладывания игральных карт, рулетки, извлечения шаров из урны и т.д. Современные физические (аппаратные) датчики представляют собой специальные устройства, генерирующие случайные числа на основе преобразования случайных шумов естественного или искусственного происхождения (тепловой шум, дробовой эффект в электронных лампах, радиоактивный распад и т.д.). Например, машина ERNIE 4 (electronic random number indicator equipment ),
- 1 Иногда, хотя и редко, к стандартным относят распределение, задаваемое таблицей 0 1 ... 8 9
- 0,1 0,1 ... 0,1 0,1/ с помощью которой определяют выигравшие номера в ежемесячной Британской лотерее, в качестве источника случайных величин использует тепловой шум транзисторов. У физического способа получения последовательности случайных чисел есть особенности, которые для имитационной модели являются недостатками. К ним относятся, в первую очередь, необходимость специальных мер по обеспечению стабильности источника сигнала, преобразуемого в случайные числа, и невозможность воспроизведения полученной последовательности случайных чисел.
Таблицы случайных чисел лишены указанных недостатков. Поясним, что понимается под таблицей случайных чисел. Предположим, что мы осуществили N независимых опытов, в результате которых получили случайные цифры а, а 2 ,осдг. Запись этих цифр (в порядке появления и в форме прямоугольной таблицы) даст так называемую таблицу случайных цифр. Используется она следующим образом. В ходе расчетов нам может потребоваться либо случайная цифра, либо случайное число. Если потребуется случайная цифра, то мы можем взять любую цифру из этой таблицы. То же относится к случаю целого случайного числа - для каждого разряда можно выбрать любую цифру. Если нам понадобится случайное число 0 k очередных цифр сц, а 2 , ос/, и считать, что 8 = (Хоцо^.-.о^. При этом в случае «идеальной» таблицы случайных цифр выбирать цифры из нее можно случайным образом, можно подряд, можно использовать любой алгоритм выбора, не зависящий от значений цифр таблицы, начинать с любого места таблицы, читать в любом направлении.
Первые таблицы случайных чисел были получены с помощью рулеток. Такие таблицы несколько раз издавались в виде книг. Одна из самых известных таблиц , опубликованная в 1927 г., содержала свыше 40 000 случайных цифр, «произвольно взятых из отчетов о переписи».
Историческая справка
Леонард Типпет (Leonard Henry Caleb Tippett , 1902-1985) - английский статистик, ученик К. Пирсона и Р. Фишера. В 1965-1966 гг. - президент Королевского статистического общества. С его именем связаны некоторые важные результаты в теории экстремальных значений, например распределение Фишера - Типпета и теорема Фишера - Типпета - Гнеденко.
Позже были сконструированы специальные устройства (машины), механически вырабатывающие случайные числа. Первую такую машину в 1939 г. использовали М. Дж. Кендалл и Б. Бэбингтон-Смит при создании таблиц, включающих 100 тыс. случайных цифр. В 1955 г. компания RAND Corporation опубликовала хорошо известные таблицы с миллионом случайных цифр, полученных другой машиной такого типа. Практическое применение таблиц случайных чисел ограничивается в настоящее время, как правило, задачами, в которых используются методы случайного отбора
выборок, например в социологических исследованиях или при проведении статистического приемочного контроля качества штучной продукции различного назначения.
Это интересно
В России действует ГОСТ 18321-73 (СТ СЭВ 1934-79), устанавливающий правила отбора единиц продукции в выборку при проведении статистического приемочного контроля качества, статистических методов анализа и регулирования технологических процессов для всех видов штучной продукции производственно-технического назначения и товаров народного потребления. В нем, в частности, указывается, что при отборе единиц продукции в выборку «используют таблицы случайных чисел по СТ СЭВ 546-77».
многократно применять; все числа легко воспроизводятся; и запас чисел в такой последовательности ограничен. Однако у последовательности псевдослучайных чисел есть очевидное преимущество перед таблицей: существуют простые формулы для расчета псевдослучайного числа, при этом на получение каждого числа затрачивается всего 3-5 команд, а программа расчета занимает в накопителе лишь несколько ячеек.
Алгоритмов получения последовательностей псевдослучайных чисел существует много, реализации таких алгоритмов, называемые датчиками (генераторами) псевдослучайных чисел, довольно подробно описаны в специальной литературе . Укажем несколько наиболее известных алгоритмов.
- Tippett L. Random sampling numbers. London: Cambridge University Press, 1927.
- См.: Кнут Д. Э. Искусство программирования. 3-е изд. М. : Вильямс, 2000. Т. 2. Гл. 3.Случайные числа.
Урок 15. Случай - душа игры
Вы уже научили черепашку многому. Но у нее есть еще и другие, скрытые возможности. Может ли черепашка самостоятельно сделать что-нибудь такое, что
удивит вас?
Оказывается, да! В списке датчиков черепашки есть датчик случайных чисел
:
случайный
Со случайными числами мы встречаемся часто: кидая игральную кость в детской игре, слушая в лесу кукушку-предсказательницу
или просто «загадывая любое число». Датчик случайных чисел в ЛогоМирах может принимать значение любого целого положительно-то числа от 0 до заданной в
качестве параметра границы значений.
Само число, указанноев качестве параметра датчика случайных чисел, не выпадает никогда.
Например, датчик случайный 20 может оказаться любым целым числом от 0 до 19, включая 19, датчик случайный 1000 - любым целым числом от 0 до 999, включая
999.
Вы, вероятно, удивитесь, где же здесь игра - одни числа. Но не забывайте, что в ЛогоМирах с помощью чисел можно задать и форму черепашки, и толщину
пишущего пера, и его размер, и цвет, и многое другое. Главное - правильно выбрать границу значений. Границы изменения основных параметров
черепашки приведены в таблице.
Датчик случайных чисел можно использовать в качестве параметра любой команды, например вперед
, направо
и т. п.
Задание 24.
Использование датчика случайных чисел
Организуйте при помощи датчика случайных чисел одну из предложенных ниже игр и запустите черепашку.
Игра 1: «Разноцветный экран»
1. Поместите черепашку в центр экрана.
2. Наберите в Рюкзаке команды и задайте режим Много раз
:
нов_цвет случайный 140 крась жди 10
Команда крась
выполняет те же действия, что и инструмент Заливка в графическом редакторе.
3. Озвучьте сюжет.
Игра 2: «Веселый маляр»
1. Измените игру № 1, расчертив экран линиями на произвольные участки с непрерывными границами:
2. Дополните инструкцию в Рюкзаке черепашки случайными поворотами и перемещениями:
направо случайный 360
вперед случайный 150
Задайте в Рюкзаке инструкцию перемещения черепашки (вперед 60
) с опущенным пером толщиной 60
случайного цвета (0-139) под небольшим углом (нов_курс 10
).Игра 4: «Охота»
Разработайте сюжет, в котором красная черепашка охотится за черной. Черная черепашка движется по случайной траектории, а направление движения красной черепашки управляется бегунком.
Вопросы для самоконтроля
1. Что такое датчик случайных чисел?
2. Какой параметр у датчика случайных чисел?
3. Что означает граница значений?
4. Выпадает ли когда-либо само число, указанное в качестве параметра?
Первый алгоритм для получения псевдослучайных чисел был предложен Дж. Нейманом. Его называют методом середины квадратов.
Пусть задано 4-значное число R 0 =0.9876. Возведём его в квадрат. Получим 8-значное числоR 0 2 =0.97535376. Выберем 4 средние цифры из этого числа и положимR 1 =0.5353. Затем снова возведём в квадрат и извлечём из него 4 средние цифры. ПолучимR 2 и т.д. Этот алгоритм не оправдал себя. Получалось больше чем нужно малых значенийR i .
Однако, представляет интерес исследовать качество этого генератора со смещённой вправо группой выбора цифр у R i 2 :
где a-максимальная значность дроби для данной ЭВМ (например, а=8).
b-количество знаков после запятой в числеR i (например, 5).
INT(А)- целая часть числа.
Для a=8,b=5,R 0 =0.51111111 на ПКZX-Spectrumполучается около 1200 неповторяющихся чисел.
Задание: Исследование следует проводить при варьировании а,b,R 0 . Найти при каких величинахa,b,R 0 получается наибольшая длинаLпоследовательности неповторяющихся чисел при “хороших” стохастических параметрах. Установить влияет ли величинаR 0 на качество датчика. Если влияет, то определить область “приемлемых” значений параметраR 0 . Представить результаты тестирования оптимального варианта значенийa,b,R 0 .
Мультипликативные алгоритмы. Датчик №2: Линейный конгруэнтный генератор Лемера 1951.
где U i ,M,Cиp–целые числа.
AmodB- остаток от деления нацелоAнаB,
A mod B =A-B*INT (A/B)
Генерируемая последовательность имеет повторяющийся цикл не превышающий pчисел.
Максимальный период получается при C0, но такой генератор даёт плохие стохастические результаты .
При C=0 генераторы называют мультипликативными. Они имеют лучшие стохастические параметры. Формулы их использования называют ещё методом вычетов.
Наиболее популярным для получения псевдослучайных чисел является метод вычетов по такой формуле :
где U i
,M,p-целые
числа, 0
Если выбрать U 0 иMтакими, чтобы дляR 0 =U 0 /pполучалась несократимая дробь и взятьpиMвзаимно простыми, тогда всеR i будут несократимыми дробями вида:R i =U i /p.
Получим наибольшую (но не более p) длину неповторяющейся последовательности чисел. ЗначенияU 0 ,pиMудобно выбрать из простых чисел.
Задание: Исследовать при какихU 0 ,pиMдлина последовательности неповторяющихся чисел будет не менее 10000 при «хороших» стохастических параметрах. Определить влияет ли величинаR 0 приMиp=constна статистические характеристики датчика. Если влияет, то определить область допустимых величинU 0 . Представить результаты тестирования генератора для оптимальных величинp,MиU 0 .
Датчик №3: Модификация Коробова .
где p- большое простое число, например 2027, 5087, …
М - целое число, отвечающее условиям:
n– целое число. Т.е. выбираемMблизким кp/2 из множества чиселM=p– 3 n .
Например, для p=5087 берёмn=7. Потому что 3 7 =2187, а 3 8 =6561 будет уже большеp. Итак: М=5087-2187=2900.
Получаем числа U i в интервале = и числаR i в интервале (0,1).
Задание: ПодобратьMиpпри которых получаются лучшие статистические параметры датчика и наибольшая длинаL. Выяснить влияет ли величинаR 0 на стохастические характеристики датчика и, если влияет, то определить область допустимых значенийR 0 . Представить результаты тестирования датчика для оптимальных значенийM,pиR 0 .
В программном обеспечении практически всех ЭВМ имеется встроенная функция генерации последовательности псевдослучайных квазиравномерно распределённых чисел. Однако для проведения статистического моделирования к генерации случайных чисел предъявляются повышенные требования. Качество результатов такого моделирования напрямую зависит от качества генератора равномерно распределенных случайных чисел, т.к. эти числа являются также источниками (исходными данными) для получения других случайных величин с заданным законом распределения.
К сожалению, идеальных генераторов не существует, а список их известных свойств пополняется перечнем недостатков. Это приводит к риску использования в компьютерном эксперименте плохого генератора. Поэтому перед проведением компьютерного эксперимента необходимо либо оценить качество встроенной в ЭВМ функции генерации случайных чисел, либо выбрать подходящий алгоритм генерации случайных чисел.
Для применения в вычислительной физике генератор должен обладать следующими свойствами:
Вычислительной эффективностью – это как можно меньшее время вычисления очередного цикла и объём памяти для работы генератора.
Большой длиной Lслучайной последовательности чисел. Этот период должен включать в себя, по крайней мере, необходимое для статистического эксперимента множество случайных чисел. Кроме того, опасность представляет даже приближение к концуL, что может привести к неверным результатам статистического эксперимента.
Критерий достаточной длины псевдослучайной последовательности выбирают из следующих соображений. Метод Монте-Карло заключается в многократном повторении рассчётов выходных параметров моделируемой системы, находящейся под воздействием входных параметров, флуктуирующих с заданными законами распределения. Основой реализации метода является генерация случайных чисел с равномерным распределением в интервале , из которых формируются случайные числа с заданными законами распределения. Далее производится подсчёт вероятности моделируемого события как отношение числа повторов модельных опытов с благополучным исходом к числу общего повторения опытов при заданных исходных условиях (параметрах) модели.
Для надёжного, в статистическом смысле, вычисления этой вероятности число повторений опыта можно оценить по формуле:
где
-
функция, обратная функции нормального
распределения,
-
доверительная вероятность ошибки
измерения вероятности.
Следовательно, для того чтобы ошибка не выходила за доверительный интервал с доверительной вероятностью, например =0,95 надо, чтобы число повторений опыта было не меньше:
(2.2)
Например, для
10% ошибки (
=0,1)
получим
,
а для 3% ошибки (
=0,03)
уже получим
.
Для других исходных условий модели новая серия повторений опытов должна проводиться на другой псевдослучайной последовательности. Поэтому либо функция генерации псевдослучайной последовательности должна иметь параметр, изменяющий её (например, R 0 ), либо её длина должна быть не менее:
где K - число исходных условий (точек на кривой определяемой методом Монте-Карло), N - число повторений модельного опыта при заданных исходных условиях,L - длина псевдослучайной последовательности.
Тогда каждая серия из N повторений каждого опыта будет проводиться на своем отрезке псевдослучайной последовательности.
Воспроизводимостью. Как указано выше, желательно иметь параметр, изменяющий генерацию псевдослучайных чисел. Обычно это R 0 . Поэтому очень важно, чтобы изменениеR 0 не портило качества (т.е. статистических параметров) генератора случайных чисел.
Хорошими статистическими свойствами. Это наиболее важный показатель качества генератора случайных чисел. Однако его нельзя оценить каким-либо одним критерием или тестом, т.к. не существует необходимых и достаточных критериев случайности конечной последовательности чисел. Самое большее, что можно сказать о псевдослучайной последовательности чисел это то, что она “выглядит” как случайная. Никакой один статистический критерий не является надёжным индикатором точности. По меньшей мере, необходимо использовать несколько тестов, отражающих наиболее важные стороны качества генератора случайных чисел, т.е. степени его приближения к идеальному генератору.
Поэтому, кроме тестирования генератора, чрезвычайно важна проверка его с помощью типовых задач, допускающих независимую оценку результатов аналитическими или численными методами.
Можно сказать, что представление о надёжности псевдослучайных чисел создаётся в процессе их использования с тщательной проверкой результатов всегда, когда это возможно.
Детерминированные ГПСЧ
Никакой детерминированный алгоритм не может генерировать полностью случайные числа, он может только аппроксимировать некоторые свойства случайных чисел. Как сказал Джон фон Нейман , «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений ».
Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается - начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и в среднем составляет около 2 n/2 , где n - размер внутреннего состояния в битах, хотя линейные конгруэнтные и LFSR -генераторы обладают максимальными циклами порядка 2 n . Если ГПСЧ может сходиться к слишком коротким циклам, такой ГПСЧ становится предсказуемым и является непригодным.
Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:
- Слишком короткий период/периоды.
- Последовательные значения не являются независимыми.
- Некоторые биты «менее случайны», чем другие.
- Неравномерное одномерное распределение.
- Обратимость.
В частности, алгоритм мейнфреймах, оказался очень плохим , что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.
ГПСЧ с источником энтропии или ГСЧ
Наравне с существующей необходимостью генерировать легко воспроизводимые последовательности случайных чисел, также существует необходимость генерировать совершенно непредсказуемые или попросту абсолютно случайные числа. Такие генераторы называются генераторами случайных чисел (ГСЧ - англ. random number generator, RNG ). Так как такие генераторы чаще всего применяются для генерации уникальных симметричных и асимметричных ключей для шифрования, они чаще всего строятся из комбинации криптостойкого ГПСЧ и внешнего источника энтропии (и именно такую комбинацию теперь и принято понимать под ГСЧ).
Почти все крупные производители микрочипов поставляют аппаратные ГСЧ с различными источниками энтропии, используя различные методы для их очистки от неизбежной предсказуемости. Однако на данный момент скорость сбора случайных чисел всеми существующими микрочипами (несколько тысяч бит в секунду) не соответствует быстродействию современных процессоров.
В персональных компьютерах авторы программных ГСЧ используют гораздо более быстрые источники энтропии, такие, как шум звуковой карты или счётчик тактов процессора . До появления возможности считывать значения счётчика тактов, сбор энтропии являлся наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например, смарт-картах), которые таким образом остаются уязвимыми. Многие ГСЧ до сих пор используют традиционные (устаревшие) методы сбора энтропии вроде измерения реакции пользователя (движение мыши и т. п.), как, например, в , или взаимодействия между потоками , как, например, в Java secure random.
Примеры ГСЧ и источников энтропии
Несколько примеров ГСЧ с их источниками энтропии и генераторами:
| Источник энтропии | ГПСЧ | Достоинства | Недостатки | |
|---|---|---|---|---|
| /dev/random в Linux | Счётчик тактов процессора, однако собирается только во время аппаратных прерываний | LFSR , с хешированием выхода через | Очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ (/dev/urandom ) | |
| Yarrow от Брюса Шнайера | Традиционные (устаревшие) методы | AES -256 и | Гибкий криптостойкий дизайн | Долго «нагревается», очень маленькое внутреннее состояние, слишком сильно зависит от криптостойкости выбранных алгоритмов, медленный, применим исключительно для генерации ключей |
| Генератор Леонида Юрьева | Шум звуковой карты | ? | Скорее всего, хороший и быстрый источник энтропии | Нет независимого, заведомо криптостойкого ГПСЧ, доступен исключительно в виде Windows |
| Microsoft | Встроен в Windows, не «застревает» | Маленькое внутреннее состояние, легко предсказуем | ||
| Взаимодействие между потоками | В Java другого выбора пока нет, большое внутреннее состояние | Медленный сбор энтропии | ||
| Chaos от Ruptor | Счётчик тактов процессора, собирается непрерывно | Хеширование 4096-битового внутреннего состояния на основе нелинейного варианта Marsaglia-генератора | Пока самый быстрый из всех, большое внутреннее состояние, не «застревает» | |
| RRAND от Ruptor | Счётчик тактов процессора | Зашифровывание внутреннего состояния поточным шифром | Очень быстр, внутреннее состояние произвольного размера по выбору, не «застревает» |
ГПСЧ в криптографии
Разновидностью ГПСЧ являются ГПСБ (PRBG) - генераторы псевдо-случайных бит, а так же различных поточных шифров . ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или семенем (англ. seed ), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие . Их общее предназначение - генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.
Хотя многие криптостойкие ГПСЧ или поточные шифры предлагают гораздо более «случайные» числа, такие генераторы гораздо медленнее обычных арифметических и могут быть непригодны во всякого рода исследованиях, требующих, чтобы процессор был свободен для более полезных вычислений.
В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются ISAAC, SEAL , Snow, совсем медленный теоретический алгоритм Блюма, Блюма и Шуба , а так же счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.
Аппаратные ГПСЧ
Кроме устаревших, хорошо известных LFSR-генераторов, широко применявшихся в качестве аппаратных ГПСЧ в XX веке, к сожалению, очень мало известно о современных аппаратных ГПСЧ (поточных шифрах), так как большинство из них разработано для военных целей и держатся в секрете. Почти все существующие коммерческие аппаратные ГПСЧ запатентованы и также держатся в секрете. Аппаратные ГПСЧ ограничены строгими требованиями к расходуемой памяти (чаще всего использование памяти запрещено), быстродействию (1-2 такта) и площади (несколько сотен FPGA - или
Из-за недостатка хороших аппаратных ГПСЧ производители вынуждены применять имеющиеся под рукой гораздо более медленные, но широко известные блочные шифры ( Компьютерное обозрение № 29 (2003)
