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

Question

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

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

Answer 1

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

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

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

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

Answer 2

Алоха!

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

В вычислительной среде, особенно для 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.

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

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

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

• Длина равного значения.Простой счетчик, который сбрасывается всякий раз, когда два последовательных значения, генерируемые ГСЧ, отличаются.И затем вам нужно определить порог, когда вы думаете, что счетчик показывает, что ГСБ сломан.Если вы видите 10 миллионов одинаковых значений и пространство значений больше, чем одно значение (то, которое вы видите), ваш ГСЧ, вероятно, работает не так хорошо.Esp, если значение является одним из значений ребра.Например, 0x00000 .... или 0xfffff ...

• Медиана.Если после генерации миллиона значений и равномерного распределения медианное значение сильно наклонено к одному из краев пространства значений, а не близко к середине, возможно, что-то не так.

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 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);

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

0: 100000
1: 100000
2: 100000
3: 100000
4: 100000
5: 100000
6: 100000
7: 100000
8: 100000
9: 100000