Как компьютер генерирует случайное число

Обновлено: 04.07.2024

Краткий пост о том, что я узнал о генерации случайных чисел из нашего мастер-класса с Барри Нельсоном

Случайные и псевдослучайные числа

На этой неделе у нас был мастер-класс с профессором Северо-Западного университета Барри Нельсоном. Мастер-класс полностью посвящен симуляции, методу использования компьютера для моделирования того, как система может меняться с течением времени. Мы узнали о многих системах, в основном об очередях, где система зависит от множества случайных вещей. Например, в очередях часто предполагается, что люди приходят случайным образом. Итак, чтобы смоделировать очередь, нам понадобится способ создать эту случайность с помощью компьютера. Мы делаем это путем генерации случайных чисел. Если мы сможем сгенерировать случайное число, то сможем использовать его для получения времени прибытия человека в очередь. Все бы ничего, но если число на самом деле случайное, то у нас нет возможности получить его снова. Представьте, что вы бросаете 100-гранный кубик и получаете 1. Можете ли вы просто бросить кубик еще раз и получить 1? Нет, потому что это случайно, а это значит, что любой из исходов равновероятен. Это также означает, что следующий результат совершенно не зависит от предыдущих, поэтому тот факт, что вы только что получили 1, абсолютно не имеет значения для следующего броска. Если бы нам снова и снова выпадала 1, мы бы действительно поставили под сомнение случайность кубика, как Дилберт ставит под сомнение свой генератор случайных чисел ниже.

Комикс о Дилберте, который я украл у Барри

По сути, это означает, что если бы мы использовали случайные числа для имитации поступления в очередь, мы бы получили некоторые результаты, которые никто никогда не сможет воспроизвести. Не совсем идеально в академическом мире, никто не поверит, что вы получили такие результаты. Способ обойти это — использовать псевдослучайные числа вместо фактически случайных. Псевдослучайные числа — это числа, созданные таким образом, что они выглядят случайными, но на самом деле они просто берутся одно за другим из заранее определенного списка неслучайных чисел. Список состоит из $p$ различных чисел, которые повторяются снова и снова, когда мы добираемся до $p$-го числа. Список выглядит следующим образом: $$u_1, u_2, \ldots, u_p, u_1, u_2,\ldots,u_p, \ldots ,$$, где $p$ называется периодом список. Компьютер берет некоторое начальное число и использует его для создания списка чисел с помощью некоторого алгоритма, разработанного для того, чтобы список выглядел случайным. Однако алгоритм является детерминированным (не случайным): он возвращает тот же список чисел, если он начинается с одного и того же начального числа. Это начальное число называется seed, и именно так мы делаем наши результаты воспроизводимыми. Одно и то же начальное число означает тот же список случайных чисел и, следовательно, тот же результат. Возвращаясь к моему примеру с броском 100-гранного кубика, мы можем смоделировать это в R, используя sample(1:100, 1) , который случайным образом выбирает число от 1 до 100. Если я сделаю это 3 раза без семени, то я получаю следующее:

Моделирование броска 100-гранной кости без семени

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

Получение одного и того же числа 3 раза с использованием семени

Я каждый раз получаю одно и то же число.

Мультипликативные конгруэнтные генераторы

Так как же нам получить список чисел, которые будут выглядеть случайными? Неудивительно, что это включает в себя довольно много теории чисел. Распространенной концепцией в теории чисел является арифметика по модулю. Это дает отношение между двумя числами на основе остатка, когда они делятся на другое. Например: $$a = b \text< mod >m$$ означает, что $a$ и $b$ имеют одинаковый остаток при делении на $m$, и мы говорим, что $a$ конгруэнтно $b \text m$. Обычно $a$ и $m$ известны, и мы хотим найти $b$, потому что $b$ будет меньшим числом, дающим ту же информацию, что и $a$. Примером того, когда это полезно, являются 12-часовые часы и 24-часовые часы: имея время из 24-часовых часов, мы можем преобразовать его в время 12-часовых часов на основе числа, которому оно соответствует. mod 12. Например, 15 часов в 24-часовом формате — это 3 часа в 12-часовом формате. У нас есть это $15 = 1(12) + 3$ и $3 = 0(12) + 3$. Это означает, что если $15 = b \text < mod >12$, то $b=3$, потому что оба остатка равны 3. В действительности мы могли бы решить уравнения конгруэнтности для $b$, сняв кратно $m$, пока мы не получим что-то меньшее, чем это: это будет остаток, который нам нужен.Например, чтобы вычислить $b$ так, что $99 = b \text < mod >12$, мы снова и снова берем 12 из 99, чтобы получить $87, 75, 63, 51, 39, 27 , 15, 3$. Итак, $99=3 \text < mod >12$.

Эта концепция используется при генерации случайных чисел, например, с помощью несколько конгруэнтных генераторов. Если мы хотим получить $u_i$ из приведенного выше списка, то мы можем использовать для этого следующие уравнения. Имея некоторое начальное число, $z_1$, мы можем получить список с помощью: $$z_i = az_ \text< mod >m$$ $$u_i = \frac.$$ Это рекурсивная формула, где следующее число генерируется с использованием арифметики по модулю относительно последнего. Производительность этого метода сильно изменится в зависимости от того, какие числа мы выберем для $a$ и $m$. Например, программа моделирования, о которой нам рассказал Барри, называется VBASim и использует: Я знаю, что это выглядит некрасиво, но в списке, который мы получаем, период около 2 миллиардов. Полезно, что число $2^-1$ является простым, а также самым большим числом (в то время), которое можно было представить на компьютере без использования экспоненциальной записи, т.е. записав его в виде $y \times 10^$. Второе число, $630 360 016$, было выбрано, чтобы обеспечить достижение максимального периода $2^-2$. Барри говорит нам, что в то время это был довольно хороший генератор. Несмотря на то, что 2 миллиарда кажутся большими, более современные генераторы могут создавать гораздо большие списки за миллисекунды. Однако мы надеемся, что это должно дать представление о том, как можно создавать списки.

Резюме и дополнительная литература

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

Оставить комментарий

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

Связаться

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

Крис Хоффман

< бр />

Крис Хоффман
Главный редактор

Крис Хоффман – главный редактор How-To Geek. Он писал о технологиях более десяти лет и два года был обозревателем PCWorld. Крис писал для The New York Times и Reader's Digest, давал интервью в качестве эксперта по технологиям на телевизионных станциях, таких как NBC 6 в Майами, и освещал свою работу в новостных агентствах, таких как Би-би-си. С 2011 года Крис написал более 2000 статей, которые были прочитаны почти миллиард раз — и это только здесь, в How-To Geek. Подробнее.

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

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

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

Для чего используются случайные числа

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

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

Настоящие случайные числа

Возможно, вам интересно, как компьютер может генерировать случайное число. Откуда берется эта «случайность». Если это всего лишь фрагмент компьютерного кода, возможно ли, что числа, генерируемые компьютером, могут быть предсказуемы?

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

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

Для более повседневного примера компьютер может полагаться на атмосферный шум или просто использовать точное время нажатия клавиш на клавиатуре в качестве источника непредсказуемых данных или энтропии. Например, ваш компьютер может заметить, что вы нажали клавишу ровно через 0,23423523 секунды после 14:00. Возьмите достаточно времени, связанного с этими нажатиями клавиш, и у вас будет источник энтропии, который вы можете использовать для генерации «настоящего» случайного числа. количество. Вы не предсказуемая машина, поэтому злоумышленник не может угадать точный момент, когда вы нажимаете эти клавиши. Устройство /dev/random в Linux, которое генерирует случайные числа, «блокирует» и не возвращает результат, пока не соберет достаточно энтропии, чтобы вернуть действительно случайное число.

Псевдослучайные числа

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

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

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

АНБ и аппаратный генератор случайных чисел Intel

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

Проблема здесь в том, что генератор случайных чисел — это, по сути, черный ящик, и мы не знаем, что происходит внутри него. Если бы RdRand содержал лазейку АНБ, правительство смогло бы взломать ключи шифрования, сгенерированные только с данными, предоставленными этим генератором случайных чисел.

Это серьезная проблема. В декабре 2013 года разработчики FreeBSD убрали поддержку прямого использования RdRand в качестве источника случайности, заявив, что не могут ему доверять. [Источник] Выходные данные устройства RdRand будут переданы в другой алгоритм, который добавляет дополнительную энтропию, гарантируя, что любые лазейки в генераторе случайных чисел не будут иметь значения. Linux уже работал таким образом, дополнительно рандомизируя случайные данные, поступающие от RdRand, чтобы они не были предсказуемы даже при наличии бэкдора. [Источник] В недавней AMA («Спросите меня о чем угодно») на Reddit генеральный директор Intel Брайан Кржанич не ответил на вопросы об этих опасениях. [Источник]

Конечно, это проблема не только чипов Intel. Разработчики FreeBSD также называли чипы Via по именам. Это противоречие показывает, почему так важно генерировать случайные числа, которые действительно случайны и непредсказуемы.

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

› Как генерировать случайные числа в Google Sheets
› Генерация случайных чисел в Microsoft Excel
› Зачем Windows 11 нужен TPM 2.0?
› Что такое ГСЧ в видеоиграх и почему люди его критикуют?
› Как рассчитать скользящее среднее в Microsoft Excel
› QWERTY-клавиатура — самая большая неразгаданная тайна технологий
› Сколько оперативной памяти требуется вашему ПК?
› Matter — это долгожданный стандарт умного дома

Александр Аробелидзе

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

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

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

Методы генерации случайных чисел

Настоящие случайные числа

Изображение устройства обработки с аналоговым входом и цифровым выходом. Фото Харрисона Бродбента

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

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

Таким образом, случайные числа, сгенерированные на основе такой случайности, называются "настоящими" случайными числами.

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

Что такое псевдослучайные числа?

Изображение компьютерного кода, проходящего через экран компьютера. Фото Маркуса Списке.

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

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

Генераторы случайных чисел этого типа часто называют генераторами псевдослучайных чисел, и в результате они выдают псевдослучайные числа.

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

Давайте сравним некоторые аспекты генераторов истинных случайных чисел или ГПСЧ и генераторов псевдослучайных чисел или ГПСЧ.

ГПСЧ быстрее, чем ГПСЧ. Из-за своей детерминированной природы они полезны, когда вам нужно воспроизвести последовательность случайных событий. Это очень помогает, например, при тестировании кода.

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

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

Пример алгоритма для генератора псевдослучайных чисел

Компьютер выполняет код, основанный на наборе правил, которым необходимо следовать. Для PRNG в целом эти правила вращаются вокруг следующего:

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

Теперь давайте рассмотрим пример.

Линейный конгруэнтный генератор

Этот генератор создает серию псевдослучайных чисел. При начальном начальном значении X₀ и целочисленных параметрах a в качестве множителя, b в качестве приращения и m в качестве модуля генератор определяется линейным соотношением: X_n ≡ (aX_n-1 + b)mod m. Или используя более удобный для программирования синтаксис: X_n = (a * X_n-1 + b) % m.

Каждый из этих участников должен удовлетворять следующим условиям:

m > 0 (модуль положительный),
0 < a < m (множитель положителен, но меньше модуля),
0 ≤ b < m (приращение неотрицательно, но меньше модуля) и
0 ≤ X₀< m (начальное значение неотрицательно, но меньше модуля).

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

Линейный конгруэнтный генератор — один из старейших и самых известных алгоритмов ГПСЧ.

Что касается алгоритмов генерации случайных чисел, которые могут выполняться компьютерами, то они появились еще в 1940-х и 50-х годах (например, метод средних квадратов и генератор Лемера) и продолжают писаться сегодня (Xoroshiro128+, Squares RNG, и многое другое).

Пример генератора случайных чисел

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

Я мог бы использовать функцию JavaScript Math.random() в качестве основы и генерировать выходные данные в псевдослучайных числах, как я делал это в предыдущих статьях (см. Таблица умножения — Создайте свою собственную таблицу умножения).

Но сама эта статья посвящена генерации случайных чисел. Поэтому я решил научиться собирать «истинные» данные, основанные на случайности, и поделиться своим открытием с вами.

Ниже показан «настоящий» генератор случайных чисел. Задайте параметры и нажмите «Создать».

"Одна вещь, с которой традиционные компьютерные системы не очень справляются, – это подбрасывание монеты, – говорит Стив Уорд, профессор компьютерных наук и инженерии в Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института. – «Они детерминированы, а это значит, что если вы зададите один и тот же вопрос, вы каждый раз будете получать один и тот же ответ. На самом деле такие машины специально и тщательно запрограммированы, чтобы устранить случайность в результатах. Они делают это, следуя правилам и полагаясь на алгоритмы при вычислениях».

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

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

Однако не всякая случайность псевдослучайна, – говорит Уорд. Есть способы, которыми машины могут генерировать действительно случайные числа. И важность истинной случайности нельзя недооценивать, добавляет он. «Если вы зайдете, например, на сайт онлайн-покера и знаете алгоритм и начальное число, вы можете написать программу, которая будет предсказывать карты, которые будут сданы». Он добавляет, что истинно случайные числа делают такой обратный инжиниринг невозможным. Существуют устройства, которые генерируют числа, заявляющие, что они действительно случайны. Они полагаются на непредсказуемые процессы, такие как тепловой или атмосферный шум, а не на определяемые человеком закономерности. Результаты могут быть немного смещены в сторону больших или четных чисел, но они не генерируются детерминированным алгоритмом.

Спасибо 17-летнему Акашу Джейну из Лондона, Англия, за этот вопрос.

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

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

Без повторения: последовательность не циклически повторяется. Хорошее числовое распределение: если формула выдает случайные числа от 0 до 9, количество выдаваемых ею нулей, единиц, двоек и т. д. должно быть примерно одинаковым в течение длительного периода времени. Отсутствие предсказуемости. У вас нет возможности предсказать, каким будет следующее число, если вы не знаете формулу и начальное значение (начальное значение).

Вот пример простой формулы случайных чисел из книги Кернигана и Ритчи "Язык программирования C":

Эта формула предполагает существование переменной random_seed, для которой изначально задано некоторое число. Переменная random_seed умножается на 1 103 515 245, а затем к произведению прибавляется 12 345; Затем random_seed заменяется этим новым значением. На самом деле это довольно хороший генератор псевдослучайных чисел. Он имеет хорошее распространение и не повторяется. Если вы используете его для создания случайных чисел от 0 до 9, вот первые 20 значений, которые он производит, если начальное число равно 10:

Если у вас есть 10 000 значений от 0 до 9, вот распределение:

Любая формула псевдослучайных чисел зависит от начального значения для начала последовательности. Если вы начнете с одного и того же начального числа, вы получите ту же последовательность значений из формулы. Таким образом, если вы зададите показанной выше функции rand() начальное число 10 на одном компьютере и посмотрите на поток чисел, который она производит, он будет идентичен потоку чисел, созданному на любом компьютере, который запускает ее с начальным числом 10. В случае Глобальной системы позиционирования эта воспроизводимость используется как способ дать каждому спутнику предсказуемый, но отличающийся набор значений, которые может отслеживать приемник GPS.

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

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