Как протестировать генератор случайных чисел

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

Dieharder — очень хороший набор для тестирования.

http://www.phy.duke.edu/~rgb/General/dieharder.php

И TestU01 тоже известен.

http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

Используйте тестирование хи-квадрат. Какой язык вы используете? Я могу предложить пример C++. В принципе

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

Вот подробное объяснение того, как начать. Предварительным тестом для любого RNG является тест Monobit, используемый NIST, который просто подсчитывает количество 1 и 0. http://csrc.nist.gov/groups/ST/toolkit/rng/stats_tests.html

Примечание о тестировании генератора случайных чисел: на самом деле нам не нужно слишком много тестов ГСЧ, потому что многие из них «включают» друг друга.

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

Определения: t = броски / испытания b = корзины / урны s = сеансы бросков n = наборы сеансов

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

Когда монеты подбрасываются 100 раз, ожидаемые значения составляют 53,9795 одной и 46,0205 другой, иногда больше орла, иногда больше решки. 50-50 не является ожидаемым значением упорядоченных бинов, поэтому этот тест превосходит любой частотный тест, который вместо этого ожидает 50-50.

Шаг 1: Выбор размера выборки: 100 подбрасываний/битов.

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

Ожидаемые значения для 2000 сеансов 100 бросков: 50-50 159,1784748 (Обратите внимание, что 50-50 происходит всего 7,96% времени.) 51-49 312.1146564 52-48 294.1080416 53-47 266,362 54-46 231,8335926 55-45 193,89718618618618618618618618686868686868686868686868686868686868686r8618686868686868686868686868686r8618686568656865686868686868686868686тели 5466 231, -44 155.8102392 57-43 120.2745706 58-42 89.16907819 59-41 63.47629295 60-40 43.37546685 61-39 28.4429291 62-38 17.89152 63-37 10.79171042 64-36 6.238957586 65-35 3.455422663
66-34 1.832421109 67 or more 1.747439674

Уравнение для получения точных процентов для ячеек b = 2 и бросков t = 100: оттуда для 99-1 предыдущее умножить на 100(t) разделить на 1 для 98-2 предыдущее умножить на 99(t-1) разделить на 2 для 97-3 предыдущее умножить на 98(t-2) разделить на 3. .. пропустить... для 51-49 предыдущую умножить на 52 (т-48) разделить на 49 для 50-50 предыдущую умножить на 51 (т-49) разделить на 50, потом еще раз разделить на 2.

Это уравнение работает с любым количеством бросков.

Шаг 3: Для этих 18 значений с 17 степенями свободы берется хи-квадрат, что дает результирующее значение p.

значения p выше 0,999 близки к совершенству. Может ли генератор случайных чисел слишком часто быть слишком близок к совершенству? Да, слишком предсказуемо. Ниже 0,001 обычно возникают определенные проблемы. В одном наборе тестов 300 нулей справа от запятой считаются бесконечно плохими, а 10–14 подряд — совсем плохими. Некоторые считают 6 нулей достаточно плохими, чтобы квалифицировать их как явный провал. Некоторые в целях безопасности считают достаточным 1 или 2 нуля и ошибаются. Таким образом, вместо одного значения p для одного набора, иногда обеспечивающего значение p ниже 0,01 для отличного ГСЧ, берется много наборов сеансов.

Шаг 4: Значения p передаются для прямой линии теста Колмогорова-Смирнова 0-1,0. Разные специалисты рекомендуют количество входов в тест К-С от 10 до 1000. 100 недостаточно. 200 нормально. 500 немного агрессивен.

Вот псевдокод для получения максимальной разницы K-S:

Set low := 0;  Set n := 200;  
Set ansForward := 0; Set ansBack := 0;

sort( pval [n] );
for (j := 0; j < n; j := j+1)   
 {  Set Kback := pval [ j ] - low;
    Set low := low +1 / n;    { Ranges from 0 to 1 }
    Set Kforward := low - pval [ j ];  
    if (Kforward > ansForward) Set ansForward := Kforward;
    if (Kback > ansBack) Set ansBack := Kback;
   }
{ Separate analysis can perhaps be made here on ansForward and ansBack.  Someone like Peter Brand might also examine and magnify the bottom 5% and the top 5%. }
if (ansForward > ansBack)
      return ansForward;
else
      return ansBack;   ∎

Ответ K-S не является значением p и не должен превышать 0,115 для 200 значений p. От 0,03 до 0,08 нормально для хорошего генератора случайных чисел. От 0,115 до 0,13 подозрительно.

Тест К-С очень прост. Он также достаточно эффективен.

Выше показан превосходный новый тест упорядоченной частоты. Любое ГСЧ, не прошедшее этот тест, не следует подвергать дальнейшим испытаниям и немедленно заменять. Но что дальше?

OFTest не включает тест LOR. Рекомендуется использовать тест «Длина прогонов» с размером выборки 200 000 с 15 степенями свободы, которые 200 раз подаются в тест К-С. (Обратите внимание, что ожидаемая сумма наименьшего бина LOR для «более j» равна j-му бину.)

И что потом? Для многих игр этих двух тестов достаточно. Есть склонность выбирать из NIST, Diehard, Dieharder, Crusher. (Примечание: тест Diehard Overlapping Sums неполноценен и ошибочен, а не является верной интерпретацией исходного кода Fortran Марсальи.)

Результаты нескольких RNG с n = 200.

1. LCG 134775813x + 1 mod 2^31 seed=11111: Старший бит: OFT KS: 0,0841 Пройдено. LOR KS: 0,04786 Пройдено. Монобит первых 200 000: -189 Pass. Бит 16: OFT KS: 0,5477 Ошибка. Монобит первых 200 000: 114 Pass. Все биты от 0 до 15 не проходят тест OFT, но проходят тест Monobit.

2. Часто ругаемый LCG Randu: 65539x + 0 mod 2^31 seed=11111:
   Старший бит: OFT KS: 0,03567 LOR KS: 0,07709. Монобит первых 200 000: -165 Бит 18: OFT KS: 0,15143 Монобит первых 200 000: +204 Все биты от 0 до 17 не соответствуют OFT.

3. LCG 69069x + 1 mod 2^32 seed=11111: Старший бит: OFT KS: 0,05547 LOR KS: 0,0456 Монобит 200 000: -290 Бит 17: OFT KS: 0,1467 Монобит 200 000: -193 Все биты от 0 до 13 не соответствуют ЧАСТО.

4. LCG 3141592653x + 2718281829 mod 2^35 seed=11111: Старший бит: OFT KS: 0,02868 LOR KS: 0,06117 Монобит 200 000: -69 Бит 16: OFT KS: 0,240 Монобит 200 000: -13 Все биты от 0 до 15 не соответствуют ЧАСТО.

5. LCG 23x + 0 mod 2^27 seed=11111: Старший бит: OFT KS: 0,5368 Монобит из 200 000: -235 Все биты не проходят OFT.

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

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

LWAP

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

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

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

См. раздел об исследовании Шармейн Кенни, чтобы узнать больше о тестах, которые вы можете запустить.

Это очень сложно.

Вы можете попробовать ENT с Fourmilab и сравните его с результатами их ГСЧ, HotBits. Вы также можете просмотреть Random.org.

Это тоже выглядит интересно: тесты твердолобых (хотя я с ними не работал).

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

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

На достаточно большой выборке они должны быть примерно одинаковыми.

Еще одна возможность — проверить неповторяемость. В идеале случайные числа не должны зависеть от чисел, которые были раньше. Очень простые (линейные конгруэнтные) ГПСЧ, скорее всего, в конце концов дадут вам одну и ту же последовательность чисел, но в достаточно большом наборе, который вам, вероятно, будет безразличен (если только вы серьезно не относитесь к случайности).

Для этого есть хороший инструмент: http://www.phy.duke.edu/~rgb/General/dieharder.php

например, вы можете протестировать встроенный urandom

cat /dev/random | dieharder -a -g 200

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

dieharder -a -g 202 -f random.txt

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

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

http://burtleburtle.net/bob/rand/testsfor.html

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

Если у вас нет доступа к генератору случайных чисел и вы не можете использовать его для произвольного генерирования чисел, вы не сможете проверить, является ли последовательность чисел случайной. Подумайте об этом: у вас есть генератор случайных чисел. Допустим, это универсальный генератор случайных чисел, генерирующий случайные целые числа в диапазоне [0,9]. Дана последовательность:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

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

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

Вы не можете сгенерировать настоящую случайность с помощью любого алгоритма, поэтому попытайтесь визуализировать свои результаты и проверить закономерности своими глазами. Ни один генератор случайных чисел (по алгоритму) не создаст какие-то шаблоны, о которых вы можете судить сами. Вот одна из демонстраций этой идеи: http://www.alife.co.uk/nonrandom/