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

Обновлено: 04.07.2024

Что такое случайность в компьютере? Как происходит генерация случайных чисел? В этой статье мы постарались дать простые ответы на эти вопросы.

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

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

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

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

Давайте поэкспериментируем с этой идеей и посмотрим, куда она нас приведёт.

Функция искажения будет принимать одно значение, а возвращать другое. Назовём её R.

Начнём с того, что R - это простая функция, которая всего лишь прибавляет единицу.

Если значение нашего семени 1, то R создаст ряд 1, 2, 3, 4, . Выглядит совсем не случайно, но мы дойдём до этого. Пусть теперь R добавляет константу вместо 1.

Если с равняется, например, 7, то мы получим ряд 1, 8, 15, 22, . Всё ещё не то. Очевидно, что мы упускаем то, что числа не должны только увеличиваться, они должны быть разбросаны по какому-то диапазону. Нам нужно, чтобы наша последовательность возвращалась в начало - круг из чисел!

Числовой круг

Посмотрим на циферблат часов: наш ряд начинается с 1 и идёт по кругу до 12. Но поскольку мы работаем с компьютером, пусть вместо 12 будет 0.

Теперь начиная с 1 снова будем прибавлять 7. Прогресс! Мы видим, что после 12 наш ряд начинает повторяться, независимо от того, с какого числа начать.

Здесь мы получаем очень важно свойство: если наш цикл состоит из n элементов, то максимальное число элементов, которые мы можем получить перед тем, как они начнут повторяться это n.

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

На этом этапе вы можете заметить, что некоторые числа не подходят для c. Если c = 4, и мы начали с 1, наша последовательность была бы 1, 5, 9, 1, 5, 9, 1, 5, 9, . что нам конечно же не подходит, потому что эта последовательность абсолютно не случайная. Становится понятно, что числа, которые мы выбираем для длины цикла и длины прыжка должны быть связаны особым образом.

Если вы попробуете несколько разных значений, то сможете увидеть одно свойство: m и с должны быть взаимно простыми.

До сих пор мы делали "прыжки" за счёт добавления, но что если использовать умножение? Умножим х на константу a.

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

(а - 1) должно делиться на все простые множители m
(а - 1) должно делиться на 4, если m делится на 4

Эти свойства вместе с правилом, что m и с должны быть взаимно простыми составляют теорему Халла-Добелла. Мы не будем рассматривать её доказательство, но если бы вы взяли кучу разных значений для разных констант, то могли бы прийти к тому же выводу.

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

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

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

Где начальное значение х - это семя, а - множитель, с - константа, m - оператор остатка от деления.

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

В разных языках программирования реализация линейного конгруэнтного метода отличается, то есть меняются значения констант. Например, функция случайных чисел в libc (стандартная библиотека С для Linux) использует m = 2 ^ 32, a = 1664525 и c = 1013904223. Такие компиляторы, как gcc, обычно используют эти значения.

Существуют и другие алгоритмы генерации случайных чисел, но линейный конгруэнтный метод считается классическим и лёгким для понимания. Если вы хотите глубже изучить данную тему, то обратите внимание на книгу Random Numbers Generators, в которой приведены элегантные доказательства линейного конгруэнтного метода.

Генерация случайных чисел имеет множество приложений в области информатики и особенно важна для криптографии.

Я пытался решить проблему хобби, которая требовала генерации миллиона случайных чисел. Но я быстро понял, что становится сложно сделать их уникальными. Я взял Руководство по разработке алгоритмов, чтобы прочитать о генерации случайных чисел.

У него есть следующий абзац, который я полностью не в состоянии понять.

Почему невозможно создать действительно случайные числа в любом детерминированном устройстве? Что означает это предложение?

Вы действительно спрашиваете, почему вы не можете произвести действительно случайное число на детерминированном устройстве? Разве в вопросе уже нет ответа?

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

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

За пределами компьютера, является ли случайное число действительно случайным? Брось кубик, это физика с большим количеством векторов.

@MPelletier: не совсем. Квантовая механика может (как только ученые выяснили больше из этого) может подразумевать существование истинной случайности, в зависимости от вашего определения случайности.

Нужно искать криптографически безопасный генератор псевдослучайных чисел . Большинство PRNG являются генераторами линейной конгруэнции ( next number как и линейная функция previous number ), поэтому, если вы next number строите график против, previous number вы получите график параллельных линий. CSPRNG не будет этого делать. Компромисс в том, что они медленные.

Я группирую генераторы случайных чисел на 3 категории :

Достаточно хорошо для домашней работы.
Достаточно хорош, чтобы поспорить с вашей компанией.
Достаточно хорош, чтобы сделать ставку на свою страну.

Почему невозможно создать действительно случайные числа в любом детерминированном устройстве?

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

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

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

@ Дэвид: Мы можем пойти немного дальше, чем это даже. Различные эксперименты по неравенству Белла показывают, что некоторые квантовые процессы окончательно непредсказуемы . Они могут быть случайными в некотором философском смысле, или они могут зависеть от нелокальных скрытых переменных, но любой случай препятствует надежному предсказанию.

@dmckee: да, я просто подумал, что было бы легче избежать попыток объяснить связь между неравенством Белла и коллапсом волновой функции в комментариях к prog.SE. Люди всегда могут зайти на наш сайт, если им любопытно ;-) Tangurena: правда, Эйнштейн действительно говорил это, но это просто означало, что он действительно хотел, чтобы вселенная была детерминированной. Это не так. Эксперименты, проведенные после смерти Эйнштейна, показали это довольно убедительно (исключая нелокальные скрытые переменные, иначе странность ). То, что он Эйнштейн, не означает, что он был прав во всем.

Истинная случайность подразумевает недетерминизм. Если это детерминистический, он может быть точно предсказан (это то, что означает детерминизм); если это можно предсказать, это не случайно.

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

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

Другой распространенный подход - взять текущее время в качестве начального числа для детерминированного ГСЧ ( srand(time(NULL)); на С); Криптографически говоря, это бесполезно, так как текущее время не секрет, но для таких вещей, как физическое моделирование или видеоигры, это достаточно хорошо.

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

@ThePopMachine: вы можете генерировать неповторяющуюся последовательность битов любой длины, эквивалентную неповторяющейся последовательности чисел неограниченной длины. Вы не можете сгенерировать неповторяющуюся последовательность целых чисел ограниченной величины (например, 32-разрядных); как только вы сгенерировали все перестановки 32-битных значений, последовательность должна повториться. Ты прав; мы просто говорим о разных вещах.

@ 9000: нет ласки. Вы сделали общее заявление, которое является ложным. Если вы на самом деле просто пытаетесь найти не более чем n ^ k разных последовательностей длины k для n разных значений, и поэтому оно должно повторяться, то это довольно очевидно и не интересно.

Отрывок из его книги хорошо объясняет это, на мой взгляд:

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

Я бы порекомендовал вам взять в руки копию этой книги (или что-то подобное). Понимание того, как именно работа PRNG определенно поможет вам в ваших усилиях.

Потому что Вам нужно код записи , чтобы генерирует случайные числа и код является НЕ случаен. (Это детерминировано)

Так что, если вы снова запустите свой код с точно такими же значениями Seed, вы получите ТОЧНЫЙ набор данных! Как любой разумный человек может назвать это случайным? Но он уверен , делает LOOK случайным.

Что касается того, чтобы сделать их уникальными, после генерации номера просто проверьте, есть ли у вас этот номер, если он есть, выбросьте его и сгенерируйте новый.

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

У меня есть очень простое определение псевдослучайного :

Слишком много неизвестных переменных для прогнозирования.

У меня также есть простое определение True Random :

Бесконечные неизвестные переменные.

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

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

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

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

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

@Chad: нет формулы в обычном смысле; это было исключено экспериментами EPR. Конечно, можно предположить, что все это детерминировано, но не так легко понять.

@DavidThornley, я знал, что это неправильное слово. Я думаю, что мы знаем, что я пытался сказать. Почти каждый раз, когда кто-то говорит, что что-то невозможно, кто-то в конечном итоге доказывает, что он неправ. Это человеческая природа.

Это все равно, что сказать, что в конце концов кто-то собирается создать машину, способную решить проблему остановки, потому что кто-то сказал, что это невозможно. Дело не в том, чтобы найти уравнение, оно на самом деле является случайным в соответствии со всеми проведенными экспериментами и той математикой, которая подтверждает это.

Невозможно произвести случайное число без специального оборудования. На первом курсе пара одноклассников и я предложили генератор случайных чисел, который имеет в основном AM-приемник и настроен на 4 разных канала, получает входной сигнал в аналого-цифровой преобразователь и добавляет их все (по модулю вашего максимального числа). Поскольку комбинация аналогового ввода с любого произвольного числа станций является случайной, и мы можем получить большое количество случайных чисел из A2D-преобразователя, мы предложили, что это может быть хорошим генератором. Конечно, даже это не является действительно случайным в философском смысле, хотя для большинства практических целей это может сработать.

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

Поэтому, если f (x) = z, f (x)! = Y, если y не равно z. Это функция. Представьте себе JavaScript:

Независимо от того, сколько раз вы вызываете, Add(2,3) он всегда вернет 5. Другими словами, Add () является детерминированной функцией.

Внешние факторы могут заставить Add вести себя недетерминированным образом. Например, если вы введете многопоточность в уравнение. Вклад человека также вызывает недетерминизм.

Теперь здесь все становится интересно.

Это просто говорит о том, что функция или система функций не станет внезапно недетерминированной. Другими словами, Add (2,3) не будет каким-либо образом возвращать 6 или что-либо, кроме 5, при тех же входных данных . Это невозможно.

Автор цитирования делает еще один шаг вперед.

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

Можно спорить о значении недетерминизма. Еще раз загар. Помните контекст.

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

Читайте также: