Методы генерации случайных чисел | Статья в журнале «Молодой ученый»

Библиографическое описание:

Гончарук В. С., Атаманов Ю. С., Гордеев С. Н. Методы генерации случайных чисел // Молодой ученый. — 2017. — №8. — С. 20-23. — URL https://moluch.ru/archive/142/40025/ (дата обращения: 15.08.2018).



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

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

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

Все генераторы случайных чисел делятся на два вида:

‒ True random number generator (ГНСЧ, генератор настоящих случайных чисел)

‒ Pseudo random number generator (ГПСЧ, генератор псевдослучайных чисел)

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

ГНСЧ использует в качестве механизма получения случайного числа некий физический процесс, который сам по себе является непредсказуемым. Если оцифровать такой процесс (например, шумы атмосферы), то можно использовать его для генератора случайных чисел. ГПСЧ в свою очередь использует математические алгоритмы (полностью производимые компьютером) [2].

Рассмотрим сравнительную таблицу 1, которая показывает отличия между ГНСЧ и ГПСЧ.

Таблица 1

Отличия ГНСЧ иГПСЧ

ГНСЧ

ГПСЧ

1) Механизм

Физический процесс

Математика

2) Равномерное распределение

3) Независимость

4) Скорость

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

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

В линейном конгруэнтным методе случайное число вычисляется по следующей рекуррентной формуле: , где — модуль (), — множитель (), — приращение (), — начальное значение, которое также иногда называют зерном (от англ. seed) ().

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

Рис. 1. Пример работы алгоритма при , , ,

Как видно из графика, данный метод даёт нам повторяющиеся последовательности, но задача состоит в том, чтобы максимально удлинить уникальную часть последовательности (граница длины уникальной части определяется величиной ).

Теперь пусть (рис. 2).

Рис. 2. Пример работы алгоритма при , , ,

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

Теперь в качестве возьмём большое простое число, пусть (рис. 3).

Рис. 3. Пример работы алгоритма при , , ,

Как видно, если является большим простым числом, то случайная последовательность ведёт себя вполне непредсказуемо. При удачно подобранных коэффициентах данный метод может давать достаточно случайные числа.

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

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

Литература:

  1. Генерация псевдослучайных чисел // habrahabr.ru. URL: https://habrahabr.ru/post/132217/ (дата обращения: 22.02.2017).
  2. Pseudorandom number generator // en.wikipedia.org. URL: https://en.wikipedia.org/wiki/Pseudorandom_number_generator (дата обращения: 22.02.2017).
  3. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. — 2nd ed. — Cambridge University Press, 1992. — P. 277. — ISBN 0–521–43108–5.
Основные термины (генерируются автоматически): число, случайное число, простое число, работа алгоритма, случайная последовательность, Равномерное распределение.


Похожие статьи

Исследование алгоритмов генерации простых чисел

Можно последовательно перебирать простые числа меньше заданного числа (точнее меньше ), чтобы найти все его делители.

3. Найти большое случайное простое число.

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

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

Аппаратный генератор случайных чисел | Статья в журнале...

Данная статья направлена на генерирование случайных чисел с равномерным распределением по ординатами звуковой карты.

В АГСЧ должен генерировать абсолютно случайную последовательность чисел.

О случайности псевдослучайных последовательностей

PARI, исследуемая последовательность, последовательность, случайная последовательность, тест, конечная последовательность нулей, графический тест, число, статистическое свойство последовательности, эффективная...

Обзор аппаратных генераторов случайных чисел

ГСЧ Intel использует последовательности случайных чисел, получаемые с двух тактовых генераторов, частота работы одного из которых превышает частоту другого в 100 раз. Тепловой шум с источника (полупроводникового резистора)...

Анализ процедур генерации ключей криптографических...

Основные термины (генерируются автоматически): число, критерий, интервал, равномерное распределение.

Программная реализация теста на оценку энтропии для равномерно распределенных последовательностей Draft SP 800-90b.

Прецизионный генератор псевдослучайных чисел | Статья...

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

Анализ применения гомоморфных схем шифрования...

Общая схема работы алгоритма обучения по прецедентам над конфиденциальными

Рассмотрим режим простой замены для ГОСТ 28147–89.

Каждый S-блок представляет собой перестановку чисел от 0 до 15 (конкретный вид S-блоков в стандарте не определен).

Анализ псевдослучайных последовательностей на...

Она обладает хорошими статистическими свойствами, что показано в работе []: равномерностью распределения элементов

При условии, что большое простое число, - большое число. Следовательно, при большом , построенная последовательность будем...

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Исследование алгоритмов генерации простых чисел

Можно последовательно перебирать простые числа меньше заданного числа (точнее меньше ), чтобы найти все его делители.

3. Найти большое случайное простое число.

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

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

Аппаратный генератор случайных чисел | Статья в журнале...

Данная статья направлена на генерирование случайных чисел с равномерным распределением по ординатами звуковой карты.

В АГСЧ должен генерировать абсолютно случайную последовательность чисел.

О случайности псевдослучайных последовательностей

PARI, исследуемая последовательность, последовательность, случайная последовательность, тест, конечная последовательность нулей, графический тест, число, статистическое свойство последовательности, эффективная...

Обзор аппаратных генераторов случайных чисел

ГСЧ Intel использует последовательности случайных чисел, получаемые с двух тактовых генераторов, частота работы одного из которых превышает частоту другого в 100 раз. Тепловой шум с источника (полупроводникового резистора)...

Анализ процедур генерации ключей криптографических...

Основные термины (генерируются автоматически): число, критерий, интервал, равномерное распределение.

Программная реализация теста на оценку энтропии для равномерно распределенных последовательностей Draft SP 800-90b.

Прецизионный генератор псевдослучайных чисел | Статья...

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

Анализ применения гомоморфных схем шифрования...

Общая схема работы алгоритма обучения по прецедентам над конфиденциальными

Рассмотрим режим простой замены для ГОСТ 28147–89.

Каждый S-блок представляет собой перестановку чисел от 0 до 15 (конкретный вид S-блоков в стандарте не определен).

Анализ псевдослучайных последовательностей на...

Она обладает хорошими статистическими свойствами, что показано в работе []: равномерностью распределения элементов

При условии, что большое простое число, - большое число. Следовательно, при большом , построенная последовательность будем...

Задать вопрос