Как стать автором
Обновить

Комментарии 21

Существует ли аппаратное решение с прядью блондинистых волос?
Не совсем понял вопрос, но на предмет аппаратных генераторов есть хорошие статьи здесь и здесь
НЛО прилетело и опубликовало эту надпись здесь
Да Вы правы. Распределения задают вероятность(частоту) появления числа.
причём появление того или иного значения этой величины до её измерения нельзя точно предсказать

Имелось в виду, что нельзя предсказать с вероятностью 1.
Плохое определение. Последовательность, в которой на четных местах стоят нули, а на нечетных — результаты бросков монетки — очень плохая случайная последовательность.

На самом деле, понятие «случайная последовательность» — довольно нетривиально. С точки зрения тервера все бесконечные последовательности нулей и единиц равноправны. Так что в computer science обычно используется определение либо через колмогоровскую сложность, либо через тесты разных классов.
| Последовательность будет случайной только если между символами, нету зависимости.
Ну да, конечно. Корреляция.
image
Корреляция != Зависимость
По поводу системы уравнений:
Сейчас перечитал и заметил, что даны X0, X1, X2, X3. До этого подумал что даны только X1, X2, X3 — придумал небольшую хитрость для вычисления a, c, m по трем выходам:

Допустим даны
X0
X1 = X0 * a + c (mod m),
X2 = X1 * a + c (mod m).

(X2 — X1) — (X1 — X0) = a * (X1 — X0) — (X1 — X0) (mod m)
X2 + X0 — 2*X1 = (a — 1) * (X1 — X0) + k*m

Если при выборе a, c, m для максимизации периода следовали условиям (в частности, (a — 1) делит все простые делители m), то (a — 1) ** n = s*m для некоторых n > n_0 и s=s(n). При этом n_0 не больше максимальной степени простого числа в разложении m.

Обозначим Q = (X2 — X1) — (X1 — X0). Тогда Q**n == z * m. Если взять достаточно большое n, можно вычислить z * m и высчитать c' и a' по этому модулю. Если выходное число X_i' не совпадает с соответствующим известным выходом X_i,
то можно уменьшить модуль с помощью НОД: new_mod = gcd(mod, X_i' — X_i) и пересчитать a' и c'. Опять же, если получить 4й, 5й,… выходы, то очень быстро можно восстановить реальный m, а следовательно, a и c. Есть еще куча способов быстрее восстановить m (например в в z может быть много небольших простых делителей, на которые можно поделить с помощью небольшого перебора). Кроме того, перед возведением в степерь Q можно умножить на специальным образом сформированное число, чтобы необходимое n было не слишком велико для вычислений.

Проверил на нескольких случайных a, c, m с m до 1024 — бит — восстанавливается достаточно быстро.
Как-то давно спорил по поводу генератора псевдослучайных чисел с другом, который по совместительству профессор университета Ганновера. Я сказал тогда, что проблема надумана — он доказывал мне с пеной у рта с формулами и математическими выкладками, что я не прав и (в теории) предсказать seed вполне возможно. К моему счастью он еще и неплохой программист — и понял мой такой пример (кстати в действительности используется, например у нас в генераторе):
Каждый раз разные псевдослучайные биты в initial и в seed заливаются разными потоками асинхронно всяким мусором, как то — длинна интервала (ticks) между последними heartbeat потока, каждое n-ное время ожидания (ticks) мутекса, размер некоторого пула в n-ный момент времени, xor на handle передающийся в какой-нибудь асинхронный callback, пара случайных битов из md5 какой-нибудь user credential, и т.д. и т.п. Биты строятся в seed примерно как в sha-512, причем напомню асинхронно, т.е. теоретически параллельно сразу M потоками.
Кто в теме, представляет себе на какой порядок это все отличается от того же отслеживания движений мыши пользователя…
И хоть все это и псевдослучайно, и алгоритм расчета известен, но вероятность просчитать конечный результат стремится к нулю. Что, после моей просьбы оценить эту вероятность, мой оппонент скрипя зубами и подтвердил.

А статья супер — однозначно в закладки…
Простите, причем тут генераторы энтропии и RNG?
Да я как бы на это ответил:
Некоторые разработчики считают, что если они скроют используемый ими метод генерации или придумают свой, то этого достаточно для защиты. Это очень распространённое заблуждение. Следует помнить, что есть специальные методы и приемы для поиска зависимостей в последовательности чисел.
При достаточно высоком уровне энтропии — невозможно найти какие-нибудь зависимости — их просто нет. И абсолютно неважно при этом скрыт ли алгоритм.
Когда-то у нас была лаба по оценке псевдослучайных и неслучайных последовательностей и я там использовал следующие критерии: Критерий Хи-квадрат, Критерий экстремумов, подсчет числа pi с помощью этой псевдослучайной последовательности и тест на сжимаемость последовательности с помощью метода LZMA (7-zip).

Работали они более менее нормально и если кому интересно, то могу скинуть.
На чем тест был?
На сгенерированных дефолтным генератором последовательностям и на последовательностях типа 1919191919, 01234567890123456789, 89898989898989 и т.д.
Во втором томе Кнута, как раз делается оценка используя Критерий Хи-квадрат и Критерий Колмогорова-Смирнова. Было бы интересно посмотреть ваши результаты для Критерия экстремумов.
Ну вот моя программа, только она была написана давно и код там ужасный.
Но надеюсь, что для кого-нибудь окажется полезной.
«Если у нас есть 624 последовательных числа сгенерированных Mersenne Twister, то применив этот алгоритм для этих последовательных чисел, мы получим полное состояние Mersenne Twister» а зачем это делать?
Все проще!
У нас есть seed и rand и они зависимы между собой. Связь однозначная.
Если же значения ранда модулированные, то есть mt_rand(0,N), то надо больше rand, но поверьте — 624 — это ПРОСТО ДОФИГА :)
См. www.slideshare.net/d0znpp/dcg7812-cryptographyinwebapps-14052863 слайды с 18го

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

История длинная (прямо хоть статью пиши... но в статье должен быть ответ, а у меня пока только вопрос.).

Так вот. Я занимаюсь научными расчетами, и внезапно обнаружил очень странный эффект. Если вызывать интеловский (встроенный в Intel Fortran) генератор равномерно распределенных случайных чисел (0,1) много раз подряд, то на некоторых компах (пока таких 4 из 5 протестированных) примерно через A=50 млн вызовов (точная цифра меняется, см.под спойлером) он начинает квазипериодически, с периодом около B=10 млн вызовов, возвращать NaN.

Подробности

Причем, значение параметра A сильно варьирует от запуска к запуску тестовой программы. На своем компьютере я получал первый NaN через 30-80 млн. вызовов функции RANDOM. А вот значение B очень стабильно: интервал между повторными NaN обычно меняется не более, чем на 10%.

На двух других протестированных компах значения параметров A и B примерно такие же, как у меня, а на третьем - вдвое меньше. Еще на одном компьютере NaN-ов нет вовсе. Все компьютеры 64-битные, процессоры - AMD и один Intel (не глючит один из AMD).

Сам тест тривиальный: генератор инициализируется некоторым числом, собранным из даты и времени (функция SEED), а потом много раз вызывается функция RANDOM. После теста результаты выводятся на график, типичный пример которого лежит вот здесь: FORTRAN_URAND_BUG.doc. Это файл Word, в котором кроме графиков с результатами приведена информация о результатах тестов на разных компах, а также тестовая программа (включая дизассемблер генератора случайных чисел). Там же написано, как скачать и запустить эту тестовую программу в виде exe-шника. Прошу прощения, но я пока не стал оформлять это все в более адекватном виде, так как не уверен, что мое сообщение здесь, в комментариях к статье 10-летней давности, вообще кто-то прочтет. Но если Вы вдруг сюда все-таки заглянули и заинтересовались - то пишите, оформлю по-человечески.

Будет ли аналогичный эффект наблюдаться в других языках/компиляторах, я проверить не могу - не располагаю компилятором/навыком. Но подозреваю, что у фортрана и Си базовые математические библиотеки часто общие. А другие языки могут что-то таскать из Си-шных библиотек. В общем, если этот вопрос тут кого-то заинтересует, я был бы благодарен за информацию о результатах ваших тестов и/или тестовые программы.

Для себя я пока решил вопрос так: сделал для встроенного генератора случайных чисел "обертку" (точнее, она и так там была, чтобы не думать в прикладных функциях про инициализацию генератора) и в случае isNan(Random) вызываю генератор повторно. Но внутренний дискомфорт остался. Я конечно понимаю, что баги могут быть даже в самых хорошо отлаженных и многократно протестированных функциях, но

НЕ В ФОРТРАНЕ ЖЕ ;-)))

Это конечно, шутка, но как известно, в каждой шутке есть доля шутки. А если немного серьезнее, то я, как фортранщик, всегда верил, что более дубовый и стабильный язык программирования надо еще поискать (КОБОЛ просьба не предлагать ;-). А уж базовому генератору случайных чисел и вовсе скоро 40 лет в обед стукнет, т.е. все должно быть отлажено, как часы. Однако же вот...

Ну и последний нюанс. Если собирать программу c выключенной оптимизацией, то все работает без NaN-ов. Меня это, мягко говоря, удивило, так как генератор случайных чисел, по идее, должен в обоих случаях вызываться один и тот же. Поскольку исходный текст функции RANDOM к моему компилятору не прилагается - вероятно, она цепляется их какой-то стандартной библиотеки - я полез в дизассемблер, чтобы понять разницу между двумя версиями генератора случайных чисел (сборка с оптимизацией и без нее). Сам генератор, как и следовало ожидать, действительно в обоих случаях одинаковый. Но внутри этой функции есть

.

один внешний вызов

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

Итак, я дизассемблировал две версии своей тестовой программы: с ключом оптимизации /Od (оптимизация запрещена) и /O2 (оптимизация скорости). Более подробная информация о компиляторе и ключах сборки есть в том же самом файле FORTRAN_URAND_BUG.doc, который упоминался выше. Оказалась, что сама функция-генератор случайных чисел в двух версиях идентична (с точностью до ее расположения в памяти, но это понятно).

Однако, внутри этой функции есть один внешний вызов:

005C052B  call        _for__acquire_semaphore_threaded (596C80h)

Внутри которого (после череды других call) происходит что-то уже совсем-совсем для меня непонятное:

75C34043  call        75C443C5

(...)         

75C443C5  jmp         dword ptr ds:[75BA007Ch]

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

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

Вдогонку.

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

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

Что и спешу исполнить, пока вышеназванные состояния не вернулись ;-)

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.