Детерминированные ГПСЧ
Никакой детерминированный алгоритм не может генерировать полностью случайные числа, он может только аппроксимировать некоторые свойства случайных чисел. Как сказал Джон фон Нейман , «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений ».
Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается - начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и в среднем составляет около 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)
Первый алгоритм для получения псевдослучайных чисел был предложен Дж. Нейманом. Его называют методом середины квадратов.
Пусть задано 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 .
Предлагается подход к построению биологического датчика случайных чисел, предназначенного для генерации на компьютере или планшете случайных последовательностей со скоростью порядка нескольких сотен бит в минуту. Подход основан на вычислении ряда величин, связанных со случайной реакцией пользователя на псевдослучайный процесс, отображаемый на экране компьютера. Псевдослучайный процесс реализован как возникновение и криволинейное движение кругов на экране в рамках некоторой заданной области.
Введение
Актуальность для криптографических приложений проблематики, связанной с генерацией случайных последовательностей (СП), обусловлена их использованием в криптографических системах для выработки ключевой и вспомогательной информации. Само понятие случайности имеет философские корни, что свидетельствует о его сложности. В математике существуют различные подходы к определению термина «случайность», их обзор дан, например, в нашей статье «Случайности не случайны?» . Сведения об известных подходах к определению понятия «случайность» систематизированы в таблице 1.Таблица 1. Подходы к определению случайности
| Название подхода | Авторы | Суть подхода |
| Частотный | фон Мизес (Mises), Чёрч (Church), Колмогоров, Ловеланд (Loveland) | В СП должна наблюдаться устойчивость частот встречаемости элементов. Например, знаки 0 и 1 должны встречаться независимо и с равными вероятностями не только в двоичной СП, но и в любой ее подпоследовательности, выбранной случайно и независимо от исходных условий генерации. |
| Сложностной | Колмогоров, Чейтин (Chaitin) | Любое описание реализации СП не может быть существенно короче самой этой реализации. То есть СП должна иметь сложное строение, и энтропия ее начальных элементов должна быть велика. Последовательность случайна, если ее алгоритмическая сложность близка к длине последовательности. |
| Количественный | Мартин-Лёф (Martin-Lof) | Разбиение вероятностного пространства последовательностей на неслучайные и случайные, то есть на последовательности, «не проходящие» и «проходящие» набор определенных тестов, предназначенных для выявления закономерностей. |
| Криптографический | Современный подход | Последовательность считается случайной, если вычислительная сложность поиска закономерностей не меньше заданной величины. |
При исследовании вопросов синтеза биологического датчика случайных чисел (далее – БиоДСЧ) целесообразно учитывать следующее условие: последовательность считается случайной, если доказана случайность физического источника, в частности, источник локально стационарен и вырабатывает последовательность с заданными характеристиками. Такой подход к определению случайности актуален при построении БиоДСЧ, его можно условно назвать «физическим». Выполнение условий определяет пригодность последовательности для использования в криптографических приложениях.
Известны различные способы генерации случайных чисел на компьютере, предполагающие использование осмысленных и неосмысленных действий пользователя в качестве источника случайности. К таким действиям можно отнести, например, нажатия клавиш на клавиатуре, перемещения либо клики мышью и др. Мерой случайности генерируемой последовательности является энтропия. Недостатком многих известных способов является сложность оценки количества получаемой энтропии. Подходы, связанные с измерением характеристик неосмысленных движений человека, позволяют получать в единицу времени относительно небольшую долю случайных бит, что накладывает определенные ограничения на использование генерируемых последовательностей в криптографических приложениях.
Псевдослучайный процесс и задача пользователя
Рассмотрим генерацию СП с помощью осмысленных реакций пользователя на некоторый достаточно сложно устроенный псевдослучайный процесс. А именно: в случайные моменты времени измеряются значения определенного набора меняющихся во времени величин. Затем случайные значения величин процесса представляются в виде случайной последовательности бит. Особенности криптографического приложения и среды функционирования определили ряд требований к БиоДСЧ:- Генерируемые последовательности должны быть близки по статистическим характеристикам к идеальным случайным последовательностям, в частности, полюсность (относительная частота «1») двоичной последовательности должна быть близка к 1/2.
- В ходе реализации процесса среднестатистическим пользователем скорость генерации должна быть не менее 10 бит/сек.
- Продолжительность генерации среднестатистическим пользователем 320 бит (которые соответствуют в алгоритме ГОСТ 28147-89 сумме длины ключа (256 бит) и длины синхропосылки (64 бита)) не должна превышать 30 секунд.
- Удобство работы пользователя с программой БиоДСЧ.
Круги движутся подобно проекциям шаров на бильярдном столе, при столкновениях отражаясь друг от друга и от границ рабочей области, часто меняя направление движения и имитируя в целом хаотичный процесс движения кругов по рабочей области (рис. 1).
Рисунок 1. Траектории движения центров кругов внутри рабочей области
Задача пользователя – сгенерировать М случайных бит. После появления в рабочей области последнего круга пользователь должен быстро удалить все N движущихся кругов, кликая в произвольной последовательности в площадь каждого круга мышью (в случае планшета – пальцем). Сеанс генерации некоторого количества бит СП завершается после удаления всех кругов. Если сгенерированного за один сеанс количества бит недостаточно, то сеанс повторяется столько раз, сколько необходимо для генерации М бит.
Измеряемые величины процесса
Генерация СП выполняется с помощью измерения ряда характеристик описанного псевдослучайного процесса в случайные моменты времени, определяемые реакцией пользователя. Скорость генерации бит тем выше, чем больше независимых характеристик подвергаются измерению. Независимость измеряемых характеристик означает непредсказуемость значения каждой характеристики по известным значениям других характеристик.Заметим, что каждый круг, движущийся на экране, пронумерован, разделен на 2 k равных невидимых пользователю секторов, пронумерованных числами от 0 до 2 k -1, где k – натуральное и вращается вокруг своего геометрического центра с заданной угловой скоростью. Нумерацию кругов и секторов круга пользователь не видит.
В момент попадания в круг (успешного клика либо нажатия пальцем) измеряется ряд характеристик процесса, так называемые источники энтропии. Обозначим a i точку попадания в i-й круг, i=1,2,… Тогда к измеряемым величинам целесообразно отнести:
- координаты X и Y точки a i ;
- расстояние R от центра круга до точки a i ;
- номер сектора внутри i-го круга, содержащего точку a i ;
- номер круга и др.
Результаты экспериментов
С целью определения параметров приоритетной реализации БиоДСЧ было проведено разными исполнителями порядка 10 4 сеансов. Реализованные эксперименты позволили определить области подходящих значений для параметров модели БиоДСЧ: размеры рабочей области, количество и диаметр кругов, скорость движения кругов, скорость вращения «вектора вылета кругов», количество секторов, на которые разделены круги, угловая скорость вращения кругов и др.При анализе результатов работы БиоДСЧ сделаны следующие допущения:
- регистрируемые события независимы во времени, то есть реакцию пользователя на процесс, наблюдаемый на экране, сложно тиражировать с высокой точностью как другому пользователю, так и самому пользователю;
- источники энтропии независимы, то есть невозможно предсказать значения любой характеристики по известным значениям других характеристик;
- качество выходной последовательности должно оцениваться с учетом известных подходов к определению случайности (таблица 1), а также «физического» подхода.
В соответствии с длиной генерируемых двоичных последовательностей было установлено приемлемое ограничение их полюсности p: |p-1/2|?b, где b?10 -2 .
Количество бит, получаемых из значений измеряемых величин процесса (источников энтропии), определялось эмпирическим путем на основе анализа информационной энтропии значений рассматриваемых характеристик. Эмпирически установлено, что «удаление» любого круга позволяет получить около 30 бит случайной последовательности. Следовательно, при используемых параметрах макета БиоДСЧ для генерации ключа и вектора инициализации алгоритма ГОСТ 28147-89 достаточно 1-2 сессий работы БиоДСЧ.
Направления улучшения характеристик биологических генераторов следует связать как с оптимизацией параметров данного макета, так и с исследованием других макетов БиоДСЧ.
Детерминированные ГПСЧ
Никакой детерминированный алгоритм не может генерировать полностью случайные числа, он может только аппроксимировать некоторые свойства случайных чисел. Как сказал Джон фон Нейман , «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений ».
Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается - начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и в среднем составляет около 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)
Получение и преобразование случайных чисел.
Распространены два основных способа получения случайных чисел:
1) Случайные числа вырабатываются специальной электронной приставкой (датчиком случайных чисел), устанавливаемой на ЭВМ. Реализация этого способа почти не требует дополнительных операций, кроме обращения к датчику случайных чисел.
2) Алгоритмический способ – основан на формировании случайных чисел в самой машине посредством специальной программы. Недостатком этого способа является дополнительный расход машинного времени, так как в этом случае машина выполняет операции самой электронной приставки.
Программа выработки случайных чисел заданным законом распределения может оказаться громоздкой. Поэтому случайные числа с заданным законом распределения обычно получают не непосредственно, а путем преобразования случайных чисел, имеющих какое-то стандартное распределение. Часто таким стандартным распределением является равномерное распределение (простота получения и удобство преобразования в другие законы).
Получение случайных чисел с равномерным законом наиболее выгодно получать с помощью электронной приставки, освобождающей ЭВМ от дополнительных затрат машинного времени. Получение чисто равномерного распределения на ЭВМ невозможно в силу ограниченности разрядной сетки. Поэтому вместо непрерывной совокупности чисел на интервале (0, 1) используют дискретную совокупность из 2 n чисел, где n – разрядность машинного слова.
Закон распределения такой совокупности носит название квазиравномерного . При n³20 различия между равномерным и квазиравномерным законами становятся несущественными.
Для получения квазиравномерных случайных чисел используют 2 способа:
1) генерирование случайных чисел с помощью электронной приставки путем моделирования некоторых случайных процессов;
2) получение псевдослучайных чисел с помощью специальных алгоритмов.
Для получения n -значного двоичного случайного числа по первому способу моделируется последовательность независимых случайных величин z i , принимающих значение 0 или 1. полученная последовательность 0 и 1, если рассматривать ее как дробное число, и представляет собой случайную величину квазиравномерного распределения на интервале (0, 1). Аппаратные методы получения этих чисел различаются только способом получения реализации z i .
Один из способов основан на подсчете количества радиоактивных частиц за определенный промежуток времени Dt , если число частиц за Dt четное, то z i =1 , а если нечетное, то z i =0 .
Другой способ использует шумовой эффект электронной лампы. Фиксируя значение шумового напряжения в определенные моменты времени t i , получаем значения независимых случайных величин U(t i) , т.е. напряжение (Вольт).
Величина z i определяется по закону:
где a – некоторое значение порогового напряжения.
Величина a обычно выбирается из условия:
Недостаток аппаратного способа в том, что он не позволяет применять метод двойного прогона для контроля работы алгоритма решения какой – либо задачи, так как при повторном прогоне не удается получать те же случайные числа.
Псевдослучайными называют числа, сформированные на ЭВМ с помощью специальных программ рекуррентным способом: каждое случайное число получают из предыдущего с помощью специальных преобразований.
Простейшее из этих преобразований следующее. Пусть имеется некоторое n – разрядное двоичное число из интервала nÎ (0, 1). Возведем его в квадрат, при этом получим уже 2 n разрядное число. Выделим средние n разрядов. Полученное таким образом n – разрядное число и будет новым значением случайного числа. Его опять возводим в квадрат и т.д. Такая последовательность псевдослучайна, т.к. с теоретической точки зрения она не является случайной.
Недостатком рекуррентных алгоритмов является то, что последовательности случайных чисел могут выродиться (например, будем получать только нулевую последовательность или последовательность единиц, или может проявляться периодичность).
Загрузка...