Comments 8
Они доступны узким специалистам, но сложны для понимания, и удалились из широкого обсуждения.не могу согласиться с вами. Для решения этой задачи можно использовать регистры сдвига с линейной обратной связью. Они имеют простую конструкцию, отличные (и даже доказуемые!) статистические свойства и относительно легко анализируются.
Мне кажется, что алгоритм, который генерирует информацию следующего шага на основе анализа информации предыдущего шага, не может по определению считаться истинно случайным генератором — так как вывод I(n + 1) = F(I(n)), где I(n) информация на шаге n, а F — функция с конечной детерминированностью, опирается на апостериорную (уже сгенерированную) информацию I(n).
Пусть даже мы раздобыли где-то кусок истинно случайной информации I(n). Если мы к нему применяем F, внутри которой — алгоритм конечной детерминированности (то есть от жесткой логики до ГПСП [ключевое здесь — слово Псевдо]), то I(n + 1) не может больше считаться истинно-случайным. А если F — истинно-случайный генератор, то его вывод не зависит от состояния входа — то есть от входной информации I(n), и значит, передавать ему на вход информацию бессмысленно.
Поправьте, если я неправ.
Пусть даже мы раздобыли где-то кусок истинно случайной информации I(n). Если мы к нему применяем F, внутри которой — алгоритм конечной детерминированности (то есть от жесткой логики до ГПСП [ключевое здесь — слово Псевдо]), то I(n + 1) не может больше считаться истинно-случайным. А если F — истинно-случайный генератор, то его вывод не зависит от состояния входа — то есть от входной информации I(n), и значит, передавать ему на вход информацию бессмысленно.
Поправьте, если я неправ.
это называется deterministic random bit generator :) весь вопрос в размере внутреннего состояния, обратимости функции и возможности предсказать следующие значения по истории (потому внутреннее состояние должно быть относительно большим). в криптографически стойких обычно использует функцию типа вычисления хеша (SHA256 итп), которая сложно обратима. полностью случайные только аппаратные генераторы, где используются физические процессы.
попробуйте проверить статистику с помощью 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.
Без результатов тестов утверждения о качестве не очень обоснованы. Кроме того для «легких» тестов генераторов можно использовать Adaptive Proportion Test и Repetitive Count Test, хотя последний больше на аппаратные генераторы ориентирован. Они описаны в nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90B.pdf 4.4.1 и 4.4.2.
Советую автору прочитать книжку В.А. Успенского "Четыре алгоритмических лица случайности". Станет понятно, что частотная устойчивость — это не единственное условие для того, чтобы последовательность была истинно случайной.
Одно из необходимых условий — это линейное возрастание энтропии последовательности. Или по-другому, самое короткое описание случайной последовательности должно зависеть от ее длины как O(n).
В вашем случае существует алгоритм, который последовательность достраивает, значит ее кратчайшее описание имеет длину O(1), что делает ее неслучайной.
Занятный алгоритм, но как говорили авторы комментов выше, нужна проверка полученной последовательности.
Так как не все математики обладают навыками JS, автор мог бы выложить несколько достаточно длинных последовательностей в свободный доступ. И любой желающий, проверив их своими методами, убедился бы в качестве описанного генератора.
Так как не все математики обладают навыками JS, автор мог бы выложить несколько достаточно длинных последовательностей в свободный доступ. И любой желающий, проверив их своими методами, убедился бы в качестве описанного генератора.
Код без оступов практически невозможно читать.
Sign up to leave a comment.
Программный генератор статистически безупречных случайных чисел