Программный генератор статистически безупречных случайных чисел

[uacrypto]

Они доступны узким специалистам, но сложны для понимания, и удалились из широкого обсуждения.

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

[gleb_l]

Мне кажется, что алгоритм, который генерирует информацию следующего шага на основе анализа информации предыдущего шага, не может по определению считаться истинно случайным генератором — так как вывод I(n + 1) = F(I(n)), где I(n) информация на шаге n, а F — функция с конечной детерминированностью, опирается на апостериорную (уже сгенерированную) информацию I(n).

Пусть даже мы раздобыли где-то кусок истинно случайной информации I(n). Если мы к нему применяем F, внутри которой — алгоритм конечной детерминированности (то есть от жесткой логики до ГПСП [ключевое здесь — слово Псевдо]), то I(n + 1) не может больше считаться истинно-случайным. А если F — истинно-случайный генератор, то его вывод не зависит от состояния входа — то есть от входной информации I(n), и значит, передавать ему на вход информацию бессмысленно.

Поправьте, если я неправ.

[VSukhomlinov]

это называется deterministic random bit generator :) весь вопрос в размере внутреннего состояния, обратимости функции и возможности предсказать следующие значения по истории (потому внутреннее состояние должно быть относительно большим). в криптографически стойких обычно использует функцию типа вычисления хеша (SHA256 итп), которая сложно обратима. полностью случайные только аппаратные генераторы, где используются физические процессы.

[VSukhomlinov]

попробуйте проверить статистику с помощью webhome.phy.duke.edu/~rgb/General/dieharder.php — стандартный набор тестов для проверки качества генераторов. Есть стандартные генераторы типа HMAC_DRBG, но они довольно ресурсоемкие, есть типа xoroshiro (http://prng.di.unimi.it/) — весьма неплохие.
Без результатов тестов утверждения о качестве не очень обоснованы. Кроме того для «легких» тестов генераторов можно использовать Adaptive Proportion Test и Repetitive Count Test, хотя последний больше на аппаратные генераторы ориентирован. Они описаны в nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90B.pdf 4.4.1 и 4.4.2.

[mostodont32]

Советую автору прочитать книжку В.А. Успенского "Четыре алгоритмических лица случайности". Станет понятно, что частотная устойчивость — это не единственное условие для того, чтобы последовательность была истинно случайной.
Одно из необходимых условий — это линейное возрастание энтропии последовательности. Или по-другому, самое короткое описание случайной последовательности должно зависеть от ее длины как O(n).
В вашем случае существует алгоритм, который последовательность достраивает, значит ее кратчайшее описание имеет длину O(1), что делает ее неслучайной.

[tvant]

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

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

[wataru]

Код без оступов практически невозможно читать.