Генератор случайных чисел

Министерство образования и науки Республики Казахстан

Актюбинский региональный государственный университет им.К.Жубанова

Р Е Ф Е Р А Т

Генератор случайных чисел

Выполнил: Студент группы 3иско1

Проверила: Старший преподаватель кафедры

 «Информационные системы»

Актобе 2014

ПЛАН

Введение

Основная часть

1. Способы получения случайных чисел

2. Характеристики ГСЧ

3. Применение ГСЧ

4.ГСЧ в лотереях

5.ГСЧ в криптографии

6. Генерирование равномерно распределенных случайных чисел        

7. Генерирование чисел с произвольным распределением

8. Тестирование ГСЧ

9. Генератор случайных чисел в Borland C++

10.Аппаратный ГСЧ

Список литературы

Введение

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

• тестирование алгоритмов;
• имитационное моделирование;
• некоторые задачи численного анализа;
• имитация пользовательского ввода.

Способы получения случайных чисел

Для получения случайных чисел можно использовать различные способы. В общем случае все методы генерирования случайных чисел можно разделить на аппаратные и программные. Устройства или алгоритмы получения случайных чисел называют генераторами случайных чисел (ГСЧ) или датчиками случайных чисел.

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

К программным ГСЧ относятся различные алгоритмы генерирования последовательности чисел, которая по своим характеристикам напоминает случайную. Для формирования очередного числа последовательности используются различные алгебраические преобразования. Одним из первых программных ГСЧ является метод средин квадратов, предложенный в 1946  г. Дж. фон Нейманом. Этот ГСЧ формирует следующий элемент последовательности на основе предыдущего путем возведения его в квадрат и выделения средних цифр полученного числа. Например, мы хотим получить 10-значное число и предыдущее число равнялось 5772156649. Возводим его в квадрат и получаем 33317792380594909201; значит, следующим числом будет 7923805949. Очевидным недостатком этого метода является зацикливание в случае, если очередное число будет равно нулю. Кроме того, существуют и другие сравнительно короткие циклы.

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

В дальнейшем мы будем рассматривать лишь программные генераторы псевдослучайных чисел.

Характеристики ГСЧ

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

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

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

Альтернативным решением является создание набора из большого количества случайных чисел и опубликование его в некотором словаре, называемом «одноразовым блокнотом». Тем не менее, и такие наборы обеспечивают очень ограниченный источник чисел по сравнению с тем количеством, которое требуется приложениям сетевой безопасности. Хотя данные наборы действительно обеспечивают статистическую случайность, они недостаточно безопасны, так как злоумышленник может получить копию словаря.

Никакой детерминированный алгоритм не может генерировать полностью случайные числа, он может только аппроксимировать некоторые их свойства. Как сказал Джон фон Нейман, «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений».

Любой ГСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел. Длина циклов ГСЧ зависит от самого генератора и составляет около 2n/2, где n — размер внутреннего состояния в битах, хотя линейные конгруэнтные и LFSR-генераторы обладают максимальными циклами порядка 2n. Если порождаемая последовательность ГСЧ сходится к слишком коротким циклам, то такой ГПСЧ становится предсказуемым и непригодным для практических приложений.

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

• Слишком короткий период/периоды.
• Последовательные значения не являются независимыми.
• Некоторые биты «менее случайны», чем другие.
• Неравномерное одномерное распределение.
• Обратимость.

В частности, алгоритм RANDU, десятилетиями использовавшийся на мейнфреймах, оказался очень плохим, что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.

Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, регистр сдвига с линейной обратной связью, регистр сдвига с обобщённой обратной связью.

Из современных ГПСЧ широкое распространение также получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нисимурой. Его достоинствами являются колоссальный период (219937−1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение максимум в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако, существуют алгоритмы, распознающие последовательность, порождаемую вихрем Мерсенна, как неслучайную.

Применение ГСЧ

Одна из задач, в которых применяются ГСЧ, – это грубая оценка объемов сложных областей в евклидовом пространстве более чем четырех или пяти измерений. Разумеется, сюда входит и приближенное вычисление интегралов. Обозначим область через R; обычно она определяется рядом неравенств. Предположим, что R – подмножество nмерного единичного куба K. Вычисление объема множества R методом Монте-Карло сводится к тому, чтобы случайным образом выбрать в K большое число N точек, которые с одинаковой вероятностью могут оказаться в любой части K. Затем подсчитывают число M точек, попавших в R, т.е. удовлетворяющих неравенствам, определяющим R. Тогда M/N есть оценка объема R. Можно показать, что точность такой оценки будет довольно низкой. Тем не менее, выборка из 10 000 точек обеспечит точность около 1%, если только объем не слишком близок к 0 или  1. Такой точности часто бывает достаточно, и добиться лучшего другими методами может оказаться очень трудно.

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

.

Сначала необходимо определить прямоугольную область, из которой будут выбираться случайные точки. Это может быть любая область, полностью содержащая фигуру, площадь которой требуется найти. Возьмем в качестве исходной области прямоугольник с координатами углов (0; –1) – (1; 1). Будем последовательно генерировать точки, равномерно распределенные внутри этого прямоугольника, и для каждой точки проверять неравенства, описывающие фигуру. Если точка удовлетворяет всем неравенствам, значит, она принадлежит фигуре. При достаточно большом числе таких экспериментов отношение числа точек NF, удовлетворяющих неравенствам, к общему числу сгенерированных точек NR показывает долю площади прямоугольника, которую занимает фигура. Площадь прямоугольника SR известна (в нашем случае она равна 2), площадь фигуры SF вычисляется тривиально:

.

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

Другим примером приближенного взятия определенного интеграла с помощью ГСЧ является вычисление объема шара в nмерном пространстве. Объем nмерного шара выражается формулой:

,

где Γ(z) – некоторая гамма-функция, определяемая следующим соотношением:

Γ (z+1)=z·Γ(z),

Γ(1)=1.

Таким образом, для натуральных z гамма-функция равна факториалу z. Для вычисления знаменателя можно воспользоваться известным значением

           

            :

.

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

ГСЧ в лотереях

Генератор случайных чисел для лотерей — аппаратно-программный комплекс, применяющийся в розыгрышах, в которых необходимо угадывать комбинацию из определенного количества чисел. Любое из возможных чисел имеет одинаковую вероятность появления.

Попытки создать генератор случайных чисел относятся к 3500 году до н. э. и связаны с древнеегипетской настольной игрой Сенет. В Сенете два игрока играют за две стороны. Ходы определяются с помощью 4-х плоских палочек, что и может считаться генератором случайных чисел того времени. Бросают все четыре палочки сразу. Подсчет очков происходит следующим образом: 1 палочка упала белой стороной вверх — 1 очко и дополнительный бросок; 2 — 2 очка; 3 — 3 очка, 4 — 4 и дополнительный бросок. Одна из сторон палочки черная и если все четыре палочки падали черной стороной вверх — это максимальный результат — 5 очков и дополнительный бросок.

Известный генератор случайных чисел ERNIE применялся на протяжении многих лет для определения выигрышных номеров британской лотереи.

Главные требования к ГСЧ, используемому для проведения розыгрышей:

Каждое число получено случайно, не имея ничего общего с другими числами в последовательности;

Каждое число из целого ряда имеет равные шансы на выпадение;

Каждое число имеет заданную вероятность появления в любой заданной области значений.

Самый распространенный метод генерации случайных чисел называется линейный конгруэнтный метод, но есть ещё и другой — аддитивный конгруэнтный метод. Эти методы генерируют последовательность чисел, удовлетворяющую условию случайности. Основой для использования этих и других методов генерации случайных чисел служит программное обеспечение, бесконечно генерирующее числа, независимо от того находится ли в данное время участник в процессе игры или нет. Благодаря этому исключается возможность того, что игрок сможет самостоятельно определить метод генерации, использующийся в данный момент, и «угадать» выпадающие числа.

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

В лотерее «ТОП-3» («ВГТЛ 2 «Победа») для определения победителей используется генератор случайных чисел, разработанный ООО «ОКБ САПР» специально для проведения тиражей лотереи. Аппарат формирует непрерывный поток случайных шумов, которые преобразуются в числа. В заданный момент времени из потока выхватываются текущие значения, которые и являются выигрышной комбинацией.

При использовании ГСЧ для розыгрышей лотерей, необходимо соблюдение следующих требований:

Тестирование потока чисел на случайность.

Исключение возможностей вмешательства с целью подтасовки результатов розыгрыша.

Передача результатов розыгрыша в центр обработки ставок в момент определения выигрышной комбинации с точностью до миллисекунды.

Возможность резервирования с автоматическим переключением на запасное оборудование в случае неисправности.

ГСЧ в криптографии

Разновидностью ГСЧ являются ГПСБ (PRBG) — генераторы псевдо-случайных бит, а также различных поточных шифров. ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или зерном (англ. seed), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие. Их общее предназначение — генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.

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

В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются RC4, ISAAC, SEAL, Snow, совсем медленный теоретический алгоритм Блюм — Блюма — Шуба, а также счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.

Примеры криптостойких ГСЧ Циклическое шифрование

В данном случае используется способ генерации ключа сессии из мастер-ключа. Счетчик с периодом N используется в качестве входа в шифрующее устройство. Например, в случае использования 56-битного ключа DES может использоваться счетчик с периодом 256. После каждого созданного ключа значение счетчика повышается на 1. Таким образом, псевдослучайная последовательность, полученная по данной схеме, имеет полный период: каждое выходное значение Х0, Х1,…XN-1 основано на разных значениях счетчика, поэтому Х0 ≠ X1 ≠ XN-1. Так как мастер-ключ является секретным, легко показать, что любой секретный ключ не зависит от знания одного или более предыдущих секретных ключей.

ANSI X9.17

ГПСЧ из стандарта ANSI X9.17 используется во многих приложениях финансовой безопасности и PGP. В основе этого ГПСЧ лежит тройной DES. Генератор ANSI X9.17 состоит из следующих частей:

Вход: генератором управляют два псевдослучайных входа. Один является 64-битным представлением текущих даты и времени, которые меняются каждый раз при создании числа. Другой является 64-битным исходным значением. Оно инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел.

Ключи: генератор использует три модуля тройного DES. Все три используют одну и ту же пару 56-битных ключей, которая держится в секрете и применяется только при генерации псевдослучайного числа.

Выход: выход состоит из 64-битного псевдослучайного числа и 64-битного значения, которое будет использоваться в качестве начального значения при создании следующего числа.

DTi — значение даты и времени на начало i-ой стадии генерации.

Vi — начальное значение для i-ой стадии генерации.

Ri — псевдослучайное число, созданное на i-ой стадии генерации.

K1, K2 — ключи, используемые на каждой стадии.

Тогда:

Ri = EDEK1,K2 [ EDEK1,K2 [ DTi] Vi ]

Vi+1 = EDEK1,K2 [ EDEK1,K2 [ DTi] Ri]

Схема включает использование 112-битного ключа и трех EDE-шифрований. На вход даются два псевдослучайных значения: значение даты и времени и начальное значение текущей итерации, на выходе получаются начальное значение для следующей итерации и очередное псевдослучайное значение. Даже если псевдослучайное число Ri будет скомпрометировано, вычислить Vi+1 из Ri не является возможным за разумное время, и, следовательно, следующее псевдослучайное значение Ri+1, так как для получения Vi+1 дополнительно выполняются три операции EDE.

Генерирование равномерно распределенных случайных чисел

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

xk+1  =  f(xk)

Число xk часто называется зерном (англ. seed) ГСЧ и полностью определяет текущее состояние ГСЧ и следующее генерируемое значение.

Поначалу функции f выбирались как можно более сложные и трудно понимаемые. Например, f(x) определялась как целое число, двоичное представление которого составляет средний 31 разряд 62разрядного квадрата числа x (модификация метода средин квадратов). Но отсутствие теории относительно f приводило к катастрофическим последствиям. Для метода средин квадратов это уже упоминавшееся зацикливание при обращении очередного числа в нуль. Поэтому уже довольно давно перешли к использованию функций, свойства которых вполне известны. Всякая последовательность целых чисел из интервала (0,  231–1) должна содержать повторения самое большое после 231≈109 элементов. Используя теорию чисел, можно выбрать такую функцию f, для которой наперед будет известно, что ее период максимально возможный или близкий к максимальному. Этим избегается преждевременное окончание или зацикливание последовательности. Дальнейшее использование теории чисел может более или менее предсказать характер последовательности, давая пользователю некоторую степень уверенности в том, что она будет достаточно хорошо моделировать случайную последовательность чисел.

Представим генерирование чисел в диапазоне [0;  1] рекуррентым методом графически (см. рис.  ). Очевидно, функция f(x) должна быть определена на всем отрезке [0;  1] и иметь на этом отрезке непрерывную область значений [0;  1], в противном случае генерируемые числа будут составлять лишь несобственное подмножество указанного отрезка.

       

а)                б)

Рис.  . Графическое представление рекуррентного ГСЧ:

а) с «плохой» функцией f(x); б) с «хорошей» функцией f(x).

Считается, что функция f(x) тем лучше подходит для генерирования случайных чисел, чем более плотно и равномерно ее график заполняет область x∈[0;  1], y∈[0;  1]. Например, функция, приведенная на рис.  , а, будет давать последовательность чисел с сильной корреляционной зависимостью соседних элементов. В случае функции, приведенная на рис.  , б, эта зависимость будет значительно слабее.

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

f(х)  =  (ах+с)  mod m,

где для nразрядных двоичных целых чисел m обычно равно 2n.

Конгруэнтный ГСЧ выдает псевдослучайные целые числа в интервале (0, m). Параметры x0, a и c – целые числа из той же области, выбираемые исходя из следующих соображений:

1. x0 может быть произвольно. Для проверки программы возможно x0=1. В дальнейшем в качестве x0 можно брать текущее время, преобразованное в число из интервала (0, m). Такой подход обеспечивает различные последовательности для различных запусков программы.
2. Выбор a должен удовлетворять трем требованиям (для двоичных машин):

1. a mod 8 = 5;
2. ;
3. двоичные знаки а не должны иметь очевидного шаблона.

3. В качестве c следует выбирать нечетное число, такое, что

.

Более подробные рекомендации по выбору параметров можно найти у Д.  Кнута [].

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

Генерирование чисел с произвольным распределением

Достаточно часто возникает необходимость сгенерировать последовательность случайных чисел yi, равномерно распределенных на данном конечном интервале [a,  b], с помощью ГСЧ, выдающего числа xi на интервале [0, m]. Приведение диапазона ГСЧ к нужному интервалу в этом случае осуществляется простым линейным преобразованием:

.

Распределение чисел после такого преобразования остается равномерным.

Более сложным случаем является генерирование случайных точек из некоторого множества в nмерном пространстве Rn, например, точек из некоторой области на плоскости. Рассмотрим формирование случайных точек для нескольких простых областей: прямоугольника, окружности и круга.

               

а)                б)        в)

Рис.  . Области, из которых выбираются точки

Для получения равномерно распределенных случайных чисел из прямоугольника, стороны которого параллельны осям координат (см. рис., а), достаточно извлекать из ГСЧ последовательно пары чисел, приводить их к нужным интервалам и использовать как координаты точки:

,

где uj – равномерно распределенное случайное число из отрезка [0, m].

Окружность можно представить одномерным множеством точек с угловой координатой φ, принимающей значения на интервале (0, 2π). Таким образом, декартовы координаты очередной точки можно вычислить следующим образом:

.

где uj – равномерно распределенное случайное число из интервала (0, m); r – радиус окружности.

В случае круга первое, что приходит в голову – воспользоваться полярной системой координат (ρ,  φ), в которой данное множество фактически представляет собой прямоугольник (а для него способ генерации чисел известен). Однако при переходе от полярных координат к декартовым нарушается распределение случайных чисел: оно становится неравномерным; плотность распределения в центре круга выше, чем по краям.

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

Воспользуемся полярной системой координат для генерирования точек. При этом будем выбирать угол φ равномерно распределенным на интервале (0; 2π), а распределение ρ построим следующим образом:

,

где x – равномерно распределенная на отрезке [0;  1] случайная величина. Можно показать, что при таком способе формирования координат случайные точки будут равномерно распределены по всей площади круга.

Помимо выбора из произвольного множества, часто требуется формировать числа с распределением, отличным от равномерного. Распределение обычно задается функцией плотности распределения f(x) либо функцией распределения F(x). Функция распределения в произвольной точке x показывает вероятность того, что случайная величина X окажется меньше данного значения x:

F(x)=P (X<x).

Функция плотности распределения представляет собой производную F(x):

.

Функция F(x) для любой случайной величины является неубывающей на всем интервале (–∞; +∞), стремится к  0 при x→ –∞ и к 1 при x→ +∞. Для получения случайных чисел с заданным распределением F(x) необходимо найти функцию, обратную к F(x), т.е. такую функцию G, что для всех y=F(x) выполняется G(y)=x. Это можно пояснить следующим образом. Предположим, что мы многократно выбираем число y, равномерно распределенное на интервале [0; 1]; каждому y мы ставим в соответствие некоторое x=G(y). Выбору 50000 игреков соответствует выбор 50000 иксов. Таким образом, доля выбранных y, лежащих между двумя фиксированными значениями, скажем y1 и y2, в точности равна доле x, лежащих в интервале [x1; x2]. Но вероятность первого из названных событий равна |  y2  –  y1  |, если y распределено равномерно; следовательно, верна цепочка равенств:

доля чисел в интервале [x1; x2] = доля чисел в интервале [y1; y2] =   y2  –  y1  =  F(x2)  –  F(x1)  = ,

которая и показывает, что в случае равномерного распределения игреков x имеет распределение с плотностью f(τ). Сложной проблемой в этом подходе является достаточно быстрое и точное формирование обратной функции распределения G(y).

Рассмотрим в качестве примера получение случайного числа с экспоненциальным распределением. Это распределение характеризуется одним параметром λ>0 и имеет следующие функции распределения и плотности распределения:

, x≥0;

.

Для этого распределения легко получить F–1 (y), т.е. разрешить уравнение F(x)=y. Решение имеет вид

.

Для получения x с искомым распределением нужно сгенерировать y, равномерно распределенное на (0,1), и применить эту формулу. Если говорить о практической стороне дела, то существуют более эффективные способы, в которых не используется медленная операция вычисления логарифма для каждого случайного числа. Данный способ продемонстрирован лишь как пример более общего подхода с использованием обратной функции распределения.

Тестирование ГСЧ

Качество ГСЧ в значительной мере влияет на результаты работы программ, использующих случайные числа. Поэтому все применяемые генераторы случайных чисел должны пройти перед моделированием системы предварительное тестирование, которое представляет собой комплекс проверок по различным стохастическим критериям, включая в качестве основных тесты на равномерность, стохастичность и независимость (рассматриваются только ГСЧ с равномерным распределением).

Проверка равномерности последовательностей псевдослучайных равномерно распределенных чисел {xi} может быть выполнена по гистограмме с присваиванием косвенных признаков. Суть проверки по гистограмме сводится к следующему. Выдвигается гипотеза о равномерности распределения чисел (0,  1). Затем интервал (0,  1) разбивается на m равных частей, тогда при генерации последовательности {xi} каждое из чисел xi c вероятностью , , попадет в один из подынтервалов. Всего в каждый jй подынтервал попадает Ni чисел последовательности {xi}, , причём . Относительная частота попадания случайных чисел из последовательности {xi} в каждый из подынтервалов будет равна Nj/N. Очевидно, что если числа xi принадлежат псевдослучайной квазиравномерно распределенной последовательности, то при достаточно больших N экспериментальная гистограмма (ломаная линия на рис., а) приближается к теоретической прямой 1/m. Оценка степени приближения, т.е. равномерности последовательности {xi}, может быть проведена с использованием критериев согласия.

Рис.  . Проверка равномерности последовательности

Существуют и другие способы проверки равномерности распределения.

Проверка стохастичности последовательности псевдослучайных чисел {xi} наиболее часто проводится методами комбинаций и серий. Сущность метода сводится к определению закона распределения длин участков между единицами (нулями) или закона распределения (появления) числа единиц (нулей) в n-разрядном двоичном числе Xi.

Теоретически закон появления j единиц в l разрядах двоичного числа Xi описывается, исходя из независимости отдельных разрядов, биномиальным законом распределения:

,

где        P (j,  l) – вероятность появления j единиц в l разрядах числа Xi;

p(1)  =  p(0)  =  0,5 – вероятность появления единицы и нуля в любом разряде числа Xi;

.

       

         

Тогда при фиксированной точке выборки N теоретически ожидаемое число появления случайных чисел Xi с j единицами в проверяемых l разрядах будет равно .

После нахождения теоретических и экспериментальных вероятностей P (j,  l) или чисел nj при различных значениях l  ≤  n гипотеза о стохастичности проверяется с использованием критериев согласия, которые подробно рассматриваются в курсе математической статистики.

При анализе стохастичности последовательности чисел {xi} методом серий последовательность разбивается на элементы первого и второго рода (a и b), т.е.

где 0 < p < 1.

Серией называется отрезок последовательности {xi}, состоящий из идущих друг за другом элементов одного и того же рода. Число элементов в отрезке (a или b) называется длиной серии.

После разбиения последовательности {xi} на серии первого и второго рода будем иметь, например, серию вида

…..aabbbbaaabbbaabbab….

Так как случайные числа a и b в данной последовательности независимы и принадлежат последовательности {xi}, равномерно распределённой на интервале (0,  1), то теоретическая вероятность появления серии длиной j в N опытах (под опытом здесь понимается генерация числа xi и проверка условия xi < p) определится формулой Бернулли:

, , .

В случае экспериментальной проверки оцениваются частоты появления серий длиной j. В результате получаются экспериментальная и теоретическая зависимости P (j, l), сходимость которых проверяется по известным критериям, причем проверку целесообразно проводить при разных значениях l и р, 0 < р < 1.

Генератор случайных чисел в Borland C++

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

В Borland C++ (как и во многих других реализациях C/C++) используется линейный конгруэнтный ГСЧ. Длина периода этого ГСЧ составляет 232 числа.

Для работы с ГСЧ в языке C предусмотрены следующие функции:

1. int rand()

Возвращает случайное целое число в диапазоне от 0 до RAND_MAX, где RAND_MAX – некоторая константа, зависящая от конкретной реализации ГСЧ. В Borland C++ значение RAND_MAX=32767.

2. int random (int max)

Возвращает случайное целое число в диапазоне от 0 до max1.

3. void srand (unsigned seed)

Устанавливает новое зерно ГСЧ. Обычно используется для установки известного начального значения x0 при отладке программы.

4. void randomize()

Устанавливает начальное значение, полученное из текущего системного времени путем путем преобразования его в целое число. Обычно используется для сброса ГСЧ в начале программы с целью предотвращения генерирования одних и тех же последовательностей. Не рекомендуется использовать в процессе отладки, т.  к. последовательность, выбранную вызовом randomize(), сложно воспроизвести. Кроме того, не рекомендуется вызывать слишком часто или через фиксированные промежутки времени, т.  к. это снизит качество («случайность») генерируемых последовательностей.

Аппаратный ГСЧ

Аппаратный генератор случайных чисел — устройство, которое генерирует последовательности случайных чисел на основе измеряемых параметров протекающего физического процесса.

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

Аппаратные генераторы случайных чисел относительно медленны и могут производить смещенные последовательности (когда определенная последовательность чисел повторяется чаще). Использование подобных генераторов зависит от потребностей конкретной предметной области и от устройства самого генератора.

Из-за недостатка хороших аппаратных ГПСЧ производители вынуждены применять имеющиеся под рукой гораздо более медленные, но широко известные блочные шифры (DES, AES) и хеш-функции (SHA-1) в поточных режимах.

Кроме устаревших, хорошо известных LFSR-генераторов, широко применявшихся в качестве аппаратных ГПСЧ в XX веке, к сожалению, очень мало известно о современных аппаратных ГПСЧ (поточных шифрах), так как большинство из них разработано для военных целей и держатся в секрете. Почти все существующие коммерческие аппаратные ГПСЧ запатентованы или держатся в секрете. Аппаратные ГПСЧ ограничены строгими требованиями к расходуемой памяти (чаще всего использование памяти запрещено), быстродействию (1-2 такта) и площади (несколько сотен FPGA- или ASIC-ячеек). Из-за таких строгих требований к аппаратным ГПСЧ очень трудно создать криптостойкий генератор, поэтому до сих пор все известные аппаратные ГПСЧ были взломаны. Примерами таких генераторов являются Toyocrypt и LILI-128, которые оба являются LFSR-генераторами, и оба были взломаны с помощью алгебраических атак.[источник не указан 59 дней]

В некоторые микропроцессоры встроен аппаратный генератор случайных чисел, например в Intel Core i* начиная с архитектуры Ivy Bridge (коды i*-3***) встроена инструкция RdRand.

Список литературы

1. Керниган  Б. Язык программирования Си: Задачи по языку Си. / Б.  Керниган, Д.  Ритчи, А.  Фьюэр  М.: Финансы и статистика, 1985. – 192  с.
2. Керниган  Б., Ритчи Д. Язык программирования Си. М.: Финансы и статистика, 1992. – 272  с.
3. Подбельский  В.В., Фомин  С.С.  Программирование на языке Си. Учеб. пособие. М.: Финансы и статистика, 2004. 600  с.
4. Форсайт Дж. Машинные методы математических вычислений / Дж.  Форсайт, М.  Малькольм, К.  Моулер. М.: Мир, 1980. – 279  с.
5. Кнут Д. Искусство программирования, том 2. Получисленные методы / Д.  Кнут. М.: Изд. дом «Вильямс», 2007. 832  с.
6. Каханер Д. Численные методы и математическое обеспечение: Пер. с англ. / Д.  Каханер, К.  Моулер, С.  Нэш. М.: Мир, 1998. – 575  с., ил.
7. Зубинский  А. В поисках случайности  // А.  Зубинский. Компьютерное обозрение №29, 2003.