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

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

P.S: Также спрашивайте об этом, потому что оператор MySQL с помощью ORDER BY RAND() LIMIT 1 не дает убедительных результатов.

Ответ 1

Алоха!

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

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

NIST опубликовал несколько документов с рекомендациями как для генераторов псевдослучайных чисел, так и для их тестирования. Посмотрите документы NIST SP 800-22 и SP 800-20.

Как заметил кто-то другой. Если вам нужен генератор истинных случайных чисел (TRNG), вам необходимо собрать физическую энтропию. Примерами таких источников являются радиоактивный распад, космическое излучение, лавовые лампы и т.д. Предпочтительно, вам нужны источники, которые трудно манипулировать. IETF имеет RFC, который имеет некоторые хорошие рекомендации, см. RFC 4086 - Источник случайности для безопасности: http://tools.ietf.org/html/rfc4086

Что вы обычно делаете, так это собирать энтропию из одного или более (предпочтительно более одного) источника. Собранные данные затем фильтруют (отбеливают) и, наконец, используют для периодического посева хорошего PRNG. Естественно, с разными семенами.

Так работают самые современные хорошие случайные генераторы. Энтропийный коллектор, подающий PRNG, созданный с использованием криптографических примитивов, таких как симметричные шифры (например, AES) или хеш-функции. См. Например, случайный генератор Yarrow/Fortuna от Schneier, который в модифицированной форме используется во FreeBSD.

Возвращаясь к вашему вопросу о тестировании. Как заметил кто-то, Марсалья подготовил хороший набор тестов, который был кодифицирован в тестах DIEHARD. В тестах Dieharder теперь есть еще более неожиданный набор тестов: http://www.phy.duke.edu/~rgb/General/dieharder.php

Dieharder - хороший инструмент, который даст вам уверенность в том, что огромная куча чисел, поставляемых на него (собранная у вашего генератора), случайна (с хорошим качеством) или нет. Запуск Dieharder прост, но потребуется некоторое время.

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

Длина равного значения. Простой счетчик, который reset, когда два консекутивных значения, генерируемые RNG, различаются. И тогда вам нужно определить порог, когда вы думаете, что счетчик показывает, что RNG нарушен. Если вы видите 10 миллионов равных значений, а пространство значений больше одного значения (того, которое вы видите), ваш RNG, вероятно, не работает так хорошо. Esp, если значение видит, является одним из значений ребра. Например, 0x00000.... или 0xfffff...
Среднее значение. Если вы после генерации миллиона значений и имеете равномерное распределение, имеете медианное значение, которое сильно опирается на одно из краев пространства значений, не близко к середине, соприкосновение, вероятно, также несовместимо.
Дисперсия. Если вы после генерации миллиона значений не видели значений, близких к MIN и MAX пространства значений, но вместо этого имеют узкое сгенерированное пространство значений, тогда что-то также не так.

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

Я надеюсь, что это помогло в некотором роде.

Ответ 2

Вещь о случайности - это то, что вы не можете сказать, случайное или случайное возвращение из случайной функции.

^{... или...}

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

Чтобы получить реальное случайное число, вы обычно хотите взаимодействовать с внешним источником, где что-то генерируется органично. Это называется True Random Number Generator.

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

Например

For i := 1 to 1000000 do // Test the function 1.000.000 times
begin
   RandomNumber := Rand(9); // Random numbers from 0 to 9
   case RandomNumber of
      1 : Returned0 := Returned0 + 1;
      1 : Returned1 := Returned1 + 1;
      1 : Returned2 := Returned2 + 1;
      1 : Returned3 := Returned3 + 1;
      1 : Returned4 := Returned4 + 1;
      1 : Returned5 := Returned5 + 1;
      1 : Returned6 := Returned6 + 1;
      1 : Returned7 := Returned7 + 1;
      1 : Returned8 := Returned8 + 1;
      1 : Returned9 := Returned9 + 1;
   end;
end

WriteLn('0: ', Returned0);
WriteLn('1: ', Returned1);
WriteLn('2: ', Returned2);
WriteLn('3: ', Returned3);
WriteLn('4: ', Returned4);
WriteLn('5: ', Returned5);
WriteLn('6: ', Returned6);
WriteLn('7: ', Returned7);
WriteLn('8: ', Returned8);
WriteLn('9: ', Returned9);

Идеальный выход должен быть равным числом для каждого случайного выхода. Что-то вроде: