Вопрос: Как псевдослучайные и по-настоящему случайные числа различны и почему это имеет значение?


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

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

Я попробовал это в питон: Вот результат 60 миллионов рулонов. Самая высокая вариация равна 0,15. Разве это не так случайно, как это получится?

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0

648


Источник


Взгляните на статью Википедии о аппаратные генерируемые случайные числа Также см. Это - stats.stackexchange.com/questions/32794/... - steadyfish
Что вы подразумеваете под «рулонами кубиков»? Есть ли у него ручка робота и камера? - starblue
в то время как я согласен с общей сутью вашего тона, что мы часто об этом слишком беспокоимся, но он был использован в реальной жизни: en.wikipedia.org/wiki/Ronald_Dale_Harris - Grady Player
Видеть это статья о онлайн-игре в покер не содержит истинной случайности, почему это имеет значение. - Varaquilex
Если вы просто держите счетчик 0-5 и сверните кубик соответственно, 666 гориллионов раз, вы получите равное распределение. - jcora


Ответы:


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

Я получаю пять карт в руке - видимо, мы не играем в Texas Hold 'Em. Предположим, что карты раздаются мне одному, одному вам, одному ко мне, одному вам и т. Д. Поэтому у меня есть первая, третья, пятая, седьмая и девятая карты в колоде.

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

Предположим, что моя вторая карта - это три сердца. Теперь я запускаю свой RNG еще 80 миллионов раз, используя 80 миллионов семян, которые производят королеву пик в качестве первого номера. Это занимает пару секунд. Я записываю все колоды, которые производят три сердца в качестве третьей карты - вторую карту в руке. Это снова только около 2% колод, так что теперь мы упали до 2 миллионов колод.

Предположим, что третья карта в моей руке - 7 клубов. У меня есть база данных из 2 миллионов семян, которые разыгрывают мои две карты; Я запускаю свой RNG еще 2 миллиона раз, чтобы найти 2% этих колод, которые производят 7 клубов в качестве третьей карты, и мы упали до 40 тысяч колод.

Вы видите, как это происходит. Я запускаю RNG 40000 еще раз, чтобы найти все семена, которые производят мою четвертую карту, и это заводит нас до 800 колод, а затем запускает его еще 800 раз, чтобы получить ~ 20 семян, которые производят мою пятую карту, и теперь я просто создайте эти двадцать колод карт, и я знаю, что у вас есть одна из двадцати возможных рук. Более того, у меня есть очень хорошее представление о том, что я буду делать дальше.

Теперь вы видите, почему важна истинная случайность? Как вы это описываете, вы думаете, что распределение важно, но распределение не является тем, что делает процесс случайным. непредсказуемость что делает процесс случайным.

ОБНОВИТЬ

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

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

Вопросы:

  • Как различаются псевдослучайные числа и действительно случайные числа?
  • Почему разница важна?
  • Различия имеют какое-то отношение к распределению выпуска PRNG?

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

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

Мы начинаем с непроверенной колоды карт. Мы спрашиваем коробку для номера от одного до 52, то есть, TRNG(52), Какой бы номер он ни выдал, мы подсчитываем, что многие карты из нашей сортированной колоды и удаляют эту карточку. Он становится первой карточкой в ​​перетасованной колоде. Затем мы просим TRNG(51) и сделать то же самое, чтобы выбрать вторую карту и т. д.

Другой способ взглянуть на это: есть 52! = 52 x 51 x 50 ... x 2 x 1 возможных колод, что примерно равно 2226, Мы выбрали одного из них по-настоящему случайным образом.

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

Поэтому позвольте мне убедиться, что я это четко объясняю. У нас есть равномерное распределение каждого отдельного выхода TRNG(n); каждый из них выбирает число от 1 до n с вероятностью 1 / n. Кроме того, результатом этого процесса является то, что мы выбрали один из 52! возможные колоды с вероятностью 1/52 !, поэтому распределение по множеству возможных колод является также равномерная.

Отлично.

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

В СТОРОНЕ: Почему 32? Не может ли он быть посеян с номером 64 или 256 или 10000 бит? Конечно. Но (1) на практике большинство готовых PRNG засеваются 32-битным числом и (2) если у вас есть 10000 бит случайности, чтобы сделать семя, то почему вы используете PRNG? У вас уже есть источник 10000 бит случайности!

В любом случае, вернемся к тому, как работает PRNG: после его посева вы можете использовать его так же, как вы используете TRNG, То есть вы передаете ему число n, и оно возвращает вам число от 1 до n включительно. Более того, распределение этой продукции более или менее равномерное, То есть, когда мы спрашиваем PRNG для числа от 1 до 6 мы получаем 1, 2, 3, 4, 5 или 6 каждый примерно в одну шестую часть времени, независимо от того, что такое семя.

Я хочу подчеркнуть этот момент несколько раз, потому что, похоже, это путает некоторых комментаторов. Распределение PRNG равномерно по меньшей мере двумя способами. Во-первых, предположим, что мы выбираем какое-либо конкретное семя. Мы ожидаем, что последовательность PRNG(6), PRNG(6), PRNG(6)... миллион раз обеспечивал бы равномерное распределение чисел между 1 и 6. И во-вторых, если бы мы выбрали миллион разных семян и называли PRNG(6)  один раз для каждого семени снова мы ожидаем равномерного распределения чисел от 1 до 6. Единообразие PRNG по любой из этих операций не имеет отношения к атаке, которую я описываю,

Этот процесс называется псевдослучайные потому что поведение ящика на самом деле полностью детерминировано; он выбирает из одного из двух32 возможное поведение, основанное на семени. То есть, как только оно посеяно, PRNG(6), PRNG(6), PRNG(6), ...  производит последовательность чисел с равномерным распределением, но эта последовательность полностью определяемый семенем. Для данной последовательности вызовов, скажем, PRNG (52), PRNG (51) ... и т. Д., Всего 232 возможные последовательности. Семя по существу выбирает ту, которую мы получаем.

Чтобы создать колоду, сервер теперь генерирует семя. (Как? Мы вернемся к этому вопросу.) Затем они называют PRNG(52), PRNG(51) и т. д., чтобы создать колоду, аналогичную предыдущей.

Эта система подвержена атаке, описанной мной. Чтобы атаковать сервер, мы сначала опережаем семя собственной копии коробки с 0 и просим PRNG(52) и напишите это. Затем мы повторно засеваем 1, попросим PRNG(52), и напишите, что вниз, вплоть до 232-1.

Теперь покерный сервер, использующий PRNG для создания колод, должен каким-то образом генерировать семя. Неважно, как они это делают. Они могли позвонить TRNG(2^32) чтобы получить действительно случайное семя. Или они могли бы взять текущее время как семя, которое вообще не является случайным; Я знаю, в какое время это так, как ты. Пункт моей атаки заключается в том, что это не имеет значения, потому что у меня есть моя база данных, Когда я вижу свою первую карту, я могу устранить 98% возможных семян. Когда я вижу свою вторую карту, я могу устранить 98% больше и так далее, пока, в конце концов, я не смогу спуститься до нескольких возможных семян и с большой вероятностью знаю, что у вас в руке.

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

Еще один способ взглянуть на проблему заключается в том, что даже если распределение миллионов звонков PRNG(6) может быть, потому что PRNG выбирает только 232 возможное поведение, он не может генерировать каждую возможную колоду.  Он может генерировать только 232 из 2226 возможные колоды; крошечная фракция. Таким образом, распределение над множеством всех колод очень плохо. Но опять же, фундаментальная атака здесь основана на том, что мы можем успешно прогнозировать прошлого и будущего поведения PRNG из небольшой выборки ее выхода.

Позвольте мне сказать это третий или четыре раза, чтобы убедиться, что это утонет. Здесь есть три дистрибутива. Во-первых, распределение процесса, которое производит случайное 32-битное семя. Это может быть совершенно случайным, непредсказуемым и единообразным атака все равно будет работать, Во-вторых, распределение миллиона призывов к PRNG(6), Это может быть совершенно однородным, и атака все равно будет работать. В-третьих, распределение колод, выбранных псевдослучайным процессом, который я описал. Это распределение крайне плохое; может быть выбрана только небольшая часть возможных палуб IRL. Атака зависит от предсказуемость поведения ПРНГ основанный на частичном знании его продукции,

ASIDE: Эта атака требует, чтобы злоумышленник знал или мог угадать, какой именно алгоритм используется PRNG. Реально ли это или нет, это открытый вопрос. Однако, при проектировании системы безопасности вы должны проектировать ее для защиты от атак, даже если злоумышленник знает все алгоритмы в программе, Иными словами: часть системы безопасности, которая должна оставаться секретной для обеспечения безопасности системы, называется «ключом». Если ваша система зависит от ее безопасности в алгоритмах, которые вы используете, это секрет, тогда ваш ключ содержит эти алгоритмы, Это очень слабое положение!

Двигаемся дальше.

Теперь давайте предположим, что у нас есть третий магический флажок CPRNG, Это криптопрочная версия PRNG, Требуется 256-битное семя, а не 32-битное семя. Он разделяет PRNG свойство, которое семя выбирает из одного из 2256 возможное поведение. И, как и наши другие машины, у него есть свойство, что большое количество вызовов CPRNG(n) производят равномерное распределение результатов между 1 и n: каждый из них имеет 1 / n времени. Можем ли мы запустить нашу атаку?

Наша первоначальная атака требует от нас хранения 232 сопоставления от семян к PRNG(52), Но 2256 - гораздо большее число; совершенно невозможно выполнить CPRNG(52)что много времени и сохранить результаты.

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

Нет. Детали слишком сложны для объяснения, но CPRNGs продуманно разработаны так, что невозможно выводить Любые полезный факт о семени от первого выхода CPRNG(52) или из Любые подмножество выхода, независимо от того, насколько велика,

Хорошо, теперь давайте предположим, что сервер использует CPRNG для создания колод. Ему требуется 256-битное семя. Как он выбирает это семя? Если он выбирает любое значение, которое злоумышленник может предсказать то внезапно атака снова станет жизнеспособной, Если мы сможем определить, что из 2256 возможные семена, только четыре миллиарда из них, вероятно, будут выбраны сервером, тогда мы снова в бизнесе, Мы можем снова установить эту атаку, только обратив внимание на небольшое количество семян, которые могут быть сгенерированы.

Следовательно, сервер должен работать, чтобы обеспечить 256-битное число равномерно распределены - то есть, каждое возможное семя выбрано с вероятностью 1/2256, В основном сервер должен звонить TRNG(2^256)-1 для генерации семени для CPRNG,

Что делать, если я могу взломать сервер и заглянуть в него, чтобы узнать, какое семя выбрано? В этом случае злоумышленник знает полное прошлое и будущее КПРНГ, Автору сервера необходимо защититься от этой атаки! (Конечно, если я смогу успешно смонтировать эту атаку, то я, вероятно, также могу просто перенести деньги на свой банковский счет напрямую, так что, возможно, это не так интересно. Точка: семя должно быть труднодоступной тайной, и действительно случайное 256-битное число довольно сложно продумать.)

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

Хорошо, поэтому семя должно быть как секретным, так и равномерно распределенным, потому что, если это не так, мы можем установить атаку. По предположению, что распределение выходов CPRNG(n) является однородным. Как насчет распределения по множеству всех возможных колод?

Вы могли бы сказать: есть 2256 возможные последовательности, выводимые CPRNG, но есть только 2226 возможные колоды. Поэтому есть более возможные последовательности, чем колоды, поэтому мы в порядке; каждая возможная колода IRL теперь (с большой вероятностью) возможна в этой системе. И это хороший аргумент, кроме ...

2226 это только приближениеиз 52 !. Разделите его. 2256/ 52! не может быть целым числом, потому что, во-первых, 52! делится на 3, но нет силы двух! Поскольку теперь это не целый номер, мы имеем ситуацию, когда все колоды возможное, но некоторые колоды более вероятны, чем другие,

Если это неясно, рассмотрим ситуацию с меньшими числами. Предположим, что у нас есть три карты: A, B и C. Предположим, мы используем PRNG с 8-битным семенем, поэтому имеется 256 возможных семян. Существует 256 возможных выходов PRNG(3) в зависимости от семени; нет никакой возможности, чтобы одна треть из них была A, одна треть из них была B, а одна треть из них была C, потому что 256 не делится равномерно на 3. Там должно быть небольшое смещение по отношению к одному из них.

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

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

Теперь вопрос: есть ли у нас атака, основанная на этом недостатке? и ответ на практике, вероятно, не, CPRNG разработаны таким образом, чтобы если семя действительно случайное тогда невозможно вычислить разницу между CPRNG а также TRNG,

Хорошо, давайте подведем итог.

Как различаются псевдослучайные числа и действительно случайные числа?

Они отличаются показателем предсказуемости.

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

Почему разница важна?

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

  • Если TRNG используется для выбора каждой карты, система недоступна.
  • Если CPRNG используется для выбора каждой карты, система безопасна, если семя является непредсказуемым и неизвестным.
  • Если используется обычный PRNG с небольшим пространством семян, то система не защищена независимо от того, является ли семя непредсказуемым или неизвестным; достаточно небольшое пространство семян восприимчиво к атакам грубой силы, описанным мной.

Разница имеет какое-то отношение к распределению выпуска PRNG?

Равномерность распределения или отсутствие индивидуальные звонки в RNG(n) не имеет отношения к атакам, которые я описал.

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

Еще один вопрос:

Если TRNG намного лучше, чем CPRNG, что, в свою очередь, намного лучше, чем PRNG, почему кто-либо использует CPRNG или PRNG?

Две причины.

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

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

Надеюсь, теперь это намного яснее.

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


1367



Хорошо, мальчики и девочки. На этот раз достаточно комментариев. Если вы хотите обсудить это дальше, пойдите, возьмите себе чат, kthnxbye! - Ivo Flipse♦
@Eric Но семя не сбрасывается перед каждой новой колодой, не так ли? Поэтому, пока вы правы, что существует лишь относительно небольшое количество траектории мы отбираем выбор, вы точно не знаете, где на траектории вы находитесь в данный момент, а траектории пересекаются. - A.S.
Кто-то действительно сделал что-то вроде этого - EJoshuaS
Хорошая (но плотная) обработка связанных вопросов находится в разделе TAOCP от Knuth, раздел 3.5 «Что такое случайная последовательность?» (Стр. 149), начиная с освещающих определений равнораспределенных, k-распределенных и ∞-распределенных последовательностей. Псевдослучайные последовательности обсуждаются в 3.5.F (стр. 170). См. Также критерии псевдослучайности из теория сложности а также Немецкий BSI, - ShreevatsaR


Как говорит Эрик Липперт, это не просто распространение. Существуют и другие способы измерения случайности.

Один из ранних генераторов случайных чисел имеет последовательность в младшем значении бит - он чередует 0 и 1. Поэтому LSB был на 100% предсказуемым. Но вам нужно больше беспокоиться об этом. Каждый бит должен быть непредсказуемым.

Вот хороший способ подумать о проблеме. Предположим, вы генерируете 64 бит случайности. Для каждого результата возьмите первые 32 бита (A) и последние 32 бита (B) и сделайте индекс в массив x [A, B]. Теперь выполните тест миллион раз, и для каждого результата увеличьте массив на это число, то есть X [A, B] ++;

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

Если он действительно случайный, цвет должен быть однородным серым. Но вы можете получить образцы. Возьмем, к примеру, эту диаграмму «случайности» в порядковом номере TCP системы Windows NT:

Windows NT 

или даже этот из Windows 98:

Windows 98 

И вот случайность реализации маршрутизатора Cisco (IOS). Cisco ISO

Эти диаграммы любезно предоставлены Документ Михала Залевского, В этом конкретном случае, если можно предсказать, какой порядковый номер TCP будет иметь систему, вы можете олицетворять эту систему при подключении к другой системе, что позволило бы захватить соединения, перехватить связь и т. Д. И даже если мы не можем предсказать следующее число в 100% случаев, если мы можем создать новое соединение под нашим контролем, мы можем увеличить шансы на успех. И когда компьютеры могут генерировать 100 000 соединений за несколько секунд, шансы успешной атаки идут от астрономических до возможных или даже вероятных.


154



Это настолько блестяще, что он приносит слезы на глаза. Должно быть приложение, которое создает их для каждой ОС (мобильный / рабочий стол / сервер) и платформу (JVM / Javascript / etc). - HDave
Функция Windows rand () неплохая! Он создает облако, которое не имеет никаких видимых паттернов. Посмотрите мою реализацию, чтобы попробовать (и другие алгоритмы): github.com/Zalastax/visualize_random - Zalastax


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

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

Более подробную информацию о нападениях RNG можно найти в это статья в Википедии,


91



Криптографические PRNG существуют и широко используются. Они могут из семян скромного размера генерировать практически неограниченный поток случайных чисел. Нецелесообразно отличать такой поток от истинных случайных чисел, поэтому никакая часть такого потока не может быть получена никакой дополнительной информацией, и для любой практической цели цифры столь же хороши, как и истинные случайные числа. - aaaaaaaaaaaa
Я думаю, что самый простой способ объяснить это состоит в том, что нужно программировать алгоритмы генераторов с произвольным числом чисел. Это означает, что есть набор инструкций, которые выполняются. Если есть набор инструкций, он не может быть случайным. - Keltari
@Keltari Вам не хватает элемента энтропии ... Большинство RNG (по крайней мере, криптографических) собирают входные данные из внешних источников (например, движение мыши) и используют это как часть начального условия - таким образом, преобразование из A в B запрограммировано, но начальное состояние A (должен) быть неопознанным. в Linux /dev/random будет поддерживать приближение того, сколько энтропии доступно, и прекратить выдавать цифры, если он падает слишком низко. - Basic
Из любопытства - почему лавовые лампы считаются «по-настоящему случайными»? Я понимаю, что он демонстрирует довольно непредсказуемое поведение, но кто-то с достаточно твердым пониманием динамики жидкости и того, как эти жидкости взаимодействуют в гравитационной среде Земли, безусловно, может дать «предсказуемые» результаты, нет? Конечно, лавовые лампы непредсказуемы, но для меня они вовсе не случайны, но очень предсказуемы. - theGreenCabbage
@ theGreenCabbage: Я подозреваю, что лавовые лампы хаотичны. Учитывая достаточно хорошую компьютерную модель и достаточную цифру точности, вы могли (в принципе) предсказать поведение на некоторое время. Но, поскольку система хаотична, две лавовые лампы с минимальным изменением начальных условий быстро расходятся в поведении. (И этот комментарий игнорирует хаотические аттракторы.) - dmm


Я попробовал это в Python: вот результат 60 миллионов рулонов. Самая высокая вариация равна 0,15. Разве это не так случайно, как это получится?

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

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

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

Если вы посмотрите на этот вопрос об обмене стеками о распределении вероятностей для нескольких бросков кубиков, вы увидите формулу стандартного отклонения бросков N кубиков (предполагая действительно случайные результаты):

 sqrt(N * 35.0 / 12.0).

Используя эту формулу, стандартное отклонение для:

  • 1 млн. Рулонов 1708
  • 60 миллионов рулонов 13229

Если мы посмотрим на ваши результаты:

  • 1 млн. Рулонов: stddev (1000066, 999666, 1001523, 999452, 999294, 999999) 804
  • 60 миллионов рулонов: stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398) является 3827

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

Псевдо-ГСЧ имеют тенденцию перемещаться по последовательности различных чисел, начиная с семени и не пересматривая исходное число за определенный период. Например, реализация старой библиотеки C rand() функция обычно имеет период 2 ^ 32, и они будут посещать каждое число между 0 и 2 ^ 32-1 ровно один раз, прежде чем повторять семя. Итак, если вы имитировали 2 ^ 32 кубика, то кубики предварительному модулю (%) результаты будут включать в себя каждое число от 0 до 2 ^ 32, подсчеты для каждого результата 1-6 будут 715827883 или 715827882 (2 ^ 32 не кратно 6), и поэтому стандартное отклонение только тривиально выше 0. Используя приведенная выше формула, правильное стандартное отклонение для 2 ^ 32 рулонов равно 111924. В любом случае, по мере увеличения количества псевдослучайных бросков вы сходитесь к 0 стандартным отклонениям. Можно ожидать, что проблема будет значительной, если количество рулонов составляет значительную часть периода, но некоторые псевдо-ГСЧ могут проявлять худшие проблемы - или проблемы даже с меньшим количеством выборок - чем другие.

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


Чтобы дать конкретный пример: скажем, математик говорит программисту по покерным машинам, что после 60 миллионов симулированных рулонов - используется для мерцания сотен маленьких «огней» вокруг экрана, если было 10 013 229 или более шестерок, которые математик ожидает 1 stddev далеко от среднего, должна быть небольшая выплата. За Правило 68-95-99.7 (Википедия) это должно произойти 16% времени (~ 68% попадают в стандартное отклонение / только половина снаружи выше). С вашим генератором случайных чисел это примерно от 3,5 стандартных отклонений выше среднего: Under 0,025% шанс - почти нет клиентов, получающих это преимущество. См. Таблицу «Высокие отклонения» на упомянутой странице, в частности:

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |

75



Вы сравниваете яблоки и апельсины здесь. Два стандартных отклонения не имеют абсолютно никакого отношения друг к другу. - Jbeuh


Я просто написал этот генератор случайных чисел для генерации бросков кубиков

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

Вы используете его так

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

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

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


50



«Генераторы псевдослучайных чисел ... генерируют предсказуемые числа с правильным распределением». Просто потому, что PRNG не гарантирует, что он имеет идеальное распределение (на самом деле, коммерческие, по большому счету, причины, изложенные в этих ответах). Хотя они могут быть предсказуемыми при наличии достаточной информации (используемый алгоритм, начальное значение семян, выходные значения, без учета), они все еще имеют дисперсию. - Brian S
Кроме того, я знаю, но get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so on слишком изящно не говоря уже :) - Janus Troelsen
@BrianS Фактически, PRNG, который не прошел тесты распределения со временем, был бы предсказуем по определению. Таким образом, над некоторым большим N, если вы получите хотя бы небольшой путь от N / 2 голов в N-монетах, вы можете начать делать ставки на головах, и вы можете выиграть больше, чем проиграете. Точно так же, если у вас есть отличное распределение голов с хвостами, но головы всегда попадают в пары, тогда у вас снова будет рецепт победы. Распределительные тесты - это то, как вы знаете, что PRNG - это хорошо. - Jon Kiparsky
Ты забыл nonlocal next :-). - Kos
Еще лучше: Pi считается нормальный, что означает, что любая последовательность цифр любой заданной длины в любой базе появляется не чаще, чем любая другая последовательность этой длины в этой базе. Алгоритм, который при запросе N случайные биты, принимает следующий N биты pi и возвращает их («семя» - это бит, который вы начинаете), в конечном итоге должно получиться совершенно равномерное распределение. Но вы все равно не захотите этого для своего генератора - кто-то, кто знает последнюю кучу битов, которые вы создали, может найти первый раз, когда происходит последовательность, предположите, что ваше семя есть и, вероятно, будет правильным. - cpast


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

Истинное генерирование случайных чисел имеет свои цели. В компьютерной безопасности, азартных играх, большой статистической выборке и т. Д.

Если вас интересуют приложения случайных чисел, проверьте Статья в Википедии,


26



Большая проблема - когда вам нужны случайные числа, которые злоумышленник не может предсказать по соображениям безопасности. - David Schwartz
Вы уверены, что наверняка встретите время, когда вам нужно действительно случайное число. Достаточно открыть веб-страницу, которая начинается с https://... - Jan Hudec
@JanHudec: Ну, в повседневном использовании вам понадобятся безопасные случайные числа с момента открытия любой программы, задолго до того, как вы введете адресную строку: см. рандомизация размещения адресного пространства, Вот почему вещи вроде этого случается. - Reid
@JanHudec Я специально говорил в том смысле, что вам нужно будет использовать онлайн-генератор случайных чисел. Истинные случайные числа используются часто, но очень немногие люди действительно должны сами их генерировать. - Alex McKenzie
В игровых автоматах также используется PRNG, а не TRNG. Генератор работает все время, и число выбирается в то время, когда нажата кнопка поворота. Сумма PRNG и действительно случайное время нажатия кнопки составляет TRNG. - Roger Dahl


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

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

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

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

Одной из известных атак на псевдослучайный ключ является атака на 802.11b WEP, WEP имеет 104-битный длинный ключ, объединенный с 24-битным IV (счетчиком), чтобы сделать 128-битный ключ, который, в свою очередь, применяется к Алгоритм RC4 для генерации псевдослучайного ключа.

( RC4( IV + Key ) ) XOR (message)

Ключи были тесно связаны друг с другом. Здесь только IV увеличилось на 1 на каждом шаге, а все остальные остались прежними. Поскольку это не было чисто случайным, это было катастрофическим и легко разбитым. Ключ можно восстановить, проанализировав около 40000 кадров, что является вопросом минут. Если WEP использовал чисто случайный 24-битный IV, тогда он может быть безопасным до примерно 2 ^ 24 (почти 16,8 миллионов) кадров.

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


26



Я обвинял вещи WEP в плохо разработанном протоколе, используя слабый шифр. С современными потоковыми шифрами вы можете использовать счетчик как IV. - CodesInChaos
Основная проблема с WEP заключалась в повторении ключа в 2 ^ 24 (около 16 миллионов) кадров. Это было еще хуже с помощью связанных ключей, которые позволили взломать код примерно в 40000 кадров. Главное здесь, что ключ не случайный. Это тесно связано, так что это легко взломать. - Prabhu
Псевдослучайность плохо в криптографии только при генерации криптографических ключей, Это совершенно прекрасно. Действительно, RC4 - это немного больше, чем генератор псевдослучайных чисел, засеянный 128-битным расширением ключа XORed на открытый текст сообщения. - Matt


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

Вот довольно приятное видео по этой теме: http://www.youtube.com/watch?v=itaMNuWLzJo 


12



Предсказуемость! = Повторение. Хорошим примером этого является Мерсенн Твистер. В большинстве случаев после 624 Int32 вы можете предсказать все следующее число, но последовательность Mersenne Twister намного длиннее (2 ^ 19937-1). - HoLyVieR
Я не понимаю, почему этот ответ не подтолкнул стек, так как мне кажется, что это точный и краткий ответ на вопрос, по крайней мере частично. Псевдослучайные числа можно легко предсказать после некоторых ничьих, количество ничьих, изменяющихся с псевдослучайным алгоритмом «качество». Выбор «хорошего» алгоритма рассматривает аспекты: 1. каждое значение рисуется равной частотой (распределение), 2. требуется «длительное время», чтобы перезапустить последовательность в начале и начать рисовать снова те же самые числа в такой же заказ. - mins
«истинные случайные числа не являются [предсказуемыми]». На сегодня это правда. Теперь, если мы верим в теорию Большого взрыва, и у нас есть много возможностей вычислить состояние Вселенной в любое время после ВВ, основанное на физике, то ... мы можем предсказать будущее, в том числе тот факт, что Я пишу этот очень точный комментарий. Правильно? - mins
Это гипотетически верно, однако, учитывая огромную степень энтропии, вовлеченную в фактические действия реальных тел, требуемая вычислительная мощность была бы смехотворно огромной. Подумайте о континентах, охваченных компьютерами. Кроме того, из-за зависимости от предыдущего состояния необходимо сохранить состояние каждого тела в Вселенной в каждый момент времени, которое по определению потребует большего пространства, чем доступно во вселенной, полностью заполненного устройством памяти - TheEnvironmentalist
@ TheEnvironmentalist - Ах! «Континенты покрыты компьютерами» ... разве это не то, что «Руководство автостопом по Галактике»? ;-) - ysap