Ответ Дейва довольно приятно возобновить его, но, чтобы уточнить немного по второму варианту:
Реальный аппаратный генератор случайных чисел использует источник физической энтропии. Таким источником энтропии могут быть космическое излучение, электрические помехи, эффект Аванланша от диода с обратным смещением (или транзистор BJT), схема Чуа и т. Д. Чем меньше детерминированный источник энтропии, тем лучше качество случайного вывода. Идеальным источником энтропии было бы использование эффекта квантовой физики или чего-то, что не может быть смоделировано с помощью детерминированных уравнений.
Другим важным фактором, связанным с генераторами случайных чисел, является то, что источник энтропии может генерировать только ограниченное количество энтропии за единицу времени. Хорошим примером является схема Чуа: хотя она довольно случайная, она имеет очень низкую скорость и не может быть использована для реальных приложений.
Во многих процессорах / микроконтроллерах со встроенными RNG используется сдвиг тактовой частоты от 2 до 4 тактов, которые намеренно неправильно синхронизированы. Затем они используют как аналоговые, так и цифровые фильтры, чтобы еще больше рандомизировать шаблон и сдвинуть результат в регистр. Выполнение такой фильтрации требует нескольких циклов, что объясняет минимальное количество циклов, требуемых для данного тактового генератора, прежде чем будет доступно более новое значение.
Дрейф часов - это не совсем квантовый эффект, поэтому его можно смоделировать, но он достаточно случайный, поскольку он зависит от множества параметров, таких как температура, кремниевый процесс, частота работы, электрические помехи, фоновое излучение и т. Д. ,
В приложениях, где аппаратный RNG не обладает достаточной пропускной способностью (например, в криптографических приложениях с высокими требованиями), довольно часто используется аппаратный RNG в качестве начального числа для генератора псевдослучайных чисел, такого как функция rand () в sdtlib. Однако такое приложение обычно обеспечивает лучшую реализацию rand (), которая специально разработана для запуска из начального числа, которое может очень часто отбрасываться с истинными случайными значениями. В более новом процессоре Intel со встроенными аппаратными RNG часть псевдослучайного алгоритма непосредственно интегрирована в кремний, поэтому он выполняется аппаратно, обеспечивая очень высокую случайную пропускную способность.
Если вы не возражаете против самого метода rand (), это всего лишь математическое выражение, предназначенное для генерирования достаточно большого количества энтропии. Достаточно большой, зависящий от приложения: для поколений криптографических ключей случайность должна быть более высокого качества, чем случайность, необходимая для простого случайного воспроизведения в вашем любимом музыкальном проигрывателе. Очевидно, что чем выше качество случайного вывода, тем выше вычислительная стоимость случайного числа.
Операции, связанные со случайным числом, очень похожи на те, которые используются при вычислении хеша MD5 файла: они пытаются использовать своего рода битовый лавинный эффект, так что однозначное изменение начального значения изменяет весь шаблон генерации. В качестве примечания, я НЕ рекомендую использовать MD5 в качестве генератора псевдослучайных чисел; это был только пример. Это было бы неэффективно и не так случайно, но суть в том, что если вы передадите один и тот же файл алгоритму хэдинга MD5, вы всегда будете получать один и тот же детерминированный вывод, почти так же, как вы всегда получали бы один и тот же вывод из функция rand (), если вы вводите то же самое начальное число, если ваша реализация не зависит от некоторых произвольных элементов, таких как текущее время.
Две темы, которые вы наметите, могут быть описаны относительно легко:
источник
Предположим, что спроектирован механический вращатель колеса рулетки, который запитывает двигатель в течение определенного промежутка времени, ждет, когда колесо и шар остановятся, и наблюдает, в каком кармане находится шар. Обычно после каждого вращения шар и колесо будут окажутся в немного другом месте, и небольшие изменения в расположении шара после одного вращения могут иметь огромное значение в том, где он заканчивается на следующем вращении. Таким образом, даже если двигатель всегда находится под напряжением в течение одного и того же промежутка времени, карман, в котором мяч приземляется на одно вращение, не будет зависеть от того, где он приземлился ранее.
Теперь предположим, однако, что некоторые из чисел имеют или имеют небольшие углубления в них, а подшипники двигателя имеют плоские пятна. Тогда некоторые вращения были бы случайными, но после вращения, которое приводит к приземлению шара в углублении и опоре в ровном месте, следующий поворот вполне может быть смещен в сторону того же результата, что и последний поворот, в котором это произошло. Если большинство спинов не одновременно попадают в диво и плоскую точку, их существование, вероятно, не сильно повлияет на вещи. С другой стороны, если одна комбинация divot / flat окажется как раз правильной, так что шар там будет достаточно стабильно приземляться на секунду, и одна из них будет размещена так, чтобы отправить мяч обратно первому, то одна в конечном итоге некоторые крайне искаженные поведения.
Если после приземления на 4 и 23 следующее вращение - 4, это не обязательно указывает на проблему. 4 должно появиться примерно в 1/38 времени в этой ситуации. Кроме того, получение случайных данных должно просто фиксировать номер кармана, поскольку ничего не известно о том, как часто мяч должен останавливаться в различных частях кармана. Тем не менее, для записи чисел может быть полезно «наблюдать» за тем, где в кармане останавливается мяч, и следить за любыми необычными паттернами. Распределение местоположений может быть смещено вперед или назад, не указывая проблемы, но если есть узкий скачок в распределении, который может быть причиной для беспокойства.
Если последовательные показания от генератора случайных чисел статистически независимы , компенсировать смещение несложно (хотя требуемое время недетерминировано). Однако если генератор попадает в состояние, в котором показания не являются независимыми (например, циклическое состояние колеса выше), компенсация становится в принципе невозможной - таким образом, потребность в аппаратном RNG, включающем схему для обнаружения такого поведения.
источник