Comments 22
Проблема с RAND_MAX — мелочи :-) Как «радует» разнообразием используемых алгоритмов для получения «случайных» чисел всеми любимый PHP — отдельная песня! Там начиная от самых тупых LCRNG через Type3 до MersenneTwister. А над ними еще 2 функции стоят. И все это по разному работает на разных платформах (Win, Linux, BSD) и с разными патчами/настройками.
Интересно =)
расскажите подробнее, пожалуйста
расскажите подробнее, пожалуйста
Можно написать простенький PHP-скрипт, который сделает srand(0) и выведет 10 результатов rand(). В идеале, каждый запуск должен выводить одни и те же числа, в статье написано почему. В реальности, на некоторых системах будет так, а на некоторых будут разные результаты. Это — игнорирование srand и зависит от патчей безопасности.
Относительно систем с повторяющимися результатами: скрипт выдаст разные числа на Linux, BSD и Windows. В никсах обычно используется Glibc-Type3 генератор, в винде — LCRNG из Glibc, да еще и RAND_MAX маленький. В BSD тоже Type3, но свой.
Это мы рассматривали rand(void), но есть еще rand(min, max), который использует результаты rand(). А еще есть array_rand (если не путаю имя), тоже из rand() берущий данные.
Особняком стоит MersenneTwister (функции mt_*), но там я еще не разбирался. Вроде, при патчах он заменяет Type3 и LCRNG.
Относительно систем с повторяющимися результатами: скрипт выдаст разные числа на Linux, BSD и Windows. В никсах обычно используется Glibc-Type3 генератор, в винде — LCRNG из Glibc, да еще и RAND_MAX маленький. В BSD тоже Type3, но свой.
Это мы рассматривали rand(void), но есть еще rand(min, max), который использует результаты rand(). А еще есть array_rand (если не путаю имя), тоже из rand() берущий данные.
Особняком стоит MersenneTwister (функции mt_*), но там я еще не разбирался. Вроде, при патчах он заменяет Type3 и LCRNG.
Интересная статья, будем надеяться на продолжение. Интересно, что за гипотеза относительно провалившихся тестов TestU01
Спасибо! Продолжение про ГПСЧ пока не планирую, но от меня будут другие статьи. А ещё мои коллеги черкнули мне, что я забыл про RNG из состава Intel MKL, каюсь, да. Но, с другой стороны, кто лучше напишет про MKL, как не сами его авторы, так что сам жду ответного поста от них.
Ответ про гипотезу чуть ниже.
Ответ про гипотезу чуть ниже.
Изобретать своё конечно полезно, но гораздо проще взять любой современный хэш\алгоритм шифрования и использовать его как сидированный ГПСЧ с гарантированной рендомностью. Или Fortuna если совсем паранойя объяла
Было бы неплохо помимо минусов прочитать какую нибудь аргументацию
Начните с себя и аргументируйте чем предложенное вами лучше.
Например, чем не устроил LFSR? Использовать порождающий полином 64-ой степени, и на выходе будет получаться относительно качественная генерируемая последовательность при простом коде генератора…
Проблема в сидировании.
Точнее, в определении качества сида.
Я вот столкнулся на практике, программируя замену window.crypto.getRandomValues(…) для устаревших или запроприетаренных браузеров.
Так вот в браузерах (да и вообще много где) нет надежных источников энтропии, кроме пользовательского ввода. И тот — не вполне надежен, есть нюянсы короче.
Плодами моих усилий стал небольшой, но полезный скриптик
Я вот столкнулся на практике, программируя замену window.crypto.getRandomValues(…) для устаревших или запроприетаренных браузеров.
Так вот в браузерах (да и вообще много где) нет надежных источников энтропии, кроме пользовательского ввода. И тот — не вполне надежен, есть нюянсы короче.
Плодами моих усилий стал небольшой, но полезный скриптик
Хотя, чего я вам рассказываю, судя по вашему профилю, вы и так в курсе )
Проблема в сидировании.
Мсье намекает на существование алгоритмов, которые не надо сидировать?)
Я так понимаю, для задач «опытов» можно обойтись обычными getTickCount или подобным. Сид всегда гарантированно разный, а тесты всегда будут пройдены (рассматриваем случай использования сида как, например, ключа для шифрования быстрого поточного алгоритма вроде RC4. Он хоть уже и не особо стойкий, но ни чуть не медленней предложенного тут варианта).
Ну а для криптографии да, тут другой подход нужен. Собирать энтропию это искусство )
С того, что не надо изобретать велосипед, если есть существующие DRBG или PRF, удовлетворяющие вашим требованиям.
> Изобретать своё конечно полезно,
Ничего своего тут и не изобретено — алгоритмы давно известные, параметры для них подобраны не нами.
> но гораздо проще взять любой современный хэш\алгоритм шифрования
Он будет существенно сложнее, чем a*x + c (поправьте, если это не так). Это значит, что придётся или писать нечто более сложное самому, или завязываться на внешние библиотеки типа OpenSSL, внимательно сидеть и думать над их лицензией, над экспортным контролем и т.п.
> с гарантированной рендомностью
Ничто не гарантированно, как известно. Хочется знать ограничения выбранного решения, а не надеяться на авось.
> если совсем паранойя объяла
Тут дело не в том. Для нашей ситуации даже последовательность 1, 2,3, 4… подошла бы лучше, чем rand(), потому что она повторяема.
Ничего своего тут и не изобретено — алгоритмы давно известные, параметры для них подобраны не нами.
> но гораздо проще взять любой современный хэш\алгоритм шифрования
Он будет существенно сложнее, чем a*x + c (поправьте, если это не так). Это значит, что придётся или писать нечто более сложное самому, или завязываться на внешние библиотеки типа OpenSSL, внимательно сидеть и думать над их лицензией, над экспортным контролем и т.п.
> с гарантированной рендомностью
Ничто не гарантированно, как известно. Хочется знать ограничения выбранного решения, а не надеяться на авось.
> если совсем паранойя объяла
Тут дело не в том. Для нашей ситуации даже последовательность 1, 2,3, 4… подошла бы лучше, чем rand(), потому что она повторяема.
Помню эти таблицы случайных чисел по университету)) Использовали при изучении полного факторного эксперимента.
Мелькнула мысль, что если ГПСЧ выдает полностью состояние (допустим 32 бита), либо инъективную функцию от состояния, то его можно с большой вероятностью «отличить от рандома» простым общим статистическим тестом — у «правильного» рандома из примерно 2**17 выходов хотя бы два должны совпасть. У описанного ГПСЧ совпасть выходы так быстро не могут, т.к. тогда образуется период и его тоже легко вычислить.
Про криптографическую стойкость таких ГПСЧ говорить нет смысла, но это может быть проблемой и для различных экспериментов со «случайными» данными.
Про криптографическую стойкость таких ГПСЧ говорить нет смысла, но это может быть проблемой и для различных экспериментов со «случайными» данными.
По этой причине в настоящее время генераторы с размером состояния 32 бита (и периодом 2^32) уже неактуальны.
> у «правильного» рандома из примерно 2**17 выходов хотя бы два должны совпасть
Ваш анализ правильный (и подобный тест наверняка включён в TestU01), но нужно учесть объёмы памяти и времени, необходимый для его проведения, ведь надо хранить все уже сгенерированные числа и сравнивать новые поступающие с каждым из них. Для 32-битного генератора это будет порядка 2^17 * 4 = 0.5 Мбайт, а вот для 64-битного, по аналогии, это будут уже гигабайты. Ну и время будет расти экспоненциально.
> у «правильного» рандома из примерно 2**17 выходов хотя бы два должны совпасть
Ваш анализ правильный (и подобный тест наверняка включён в TestU01), но нужно учесть объёмы памяти и времени, необходимый для его проведения, ведь надо хранить все уже сгенерированные числа и сравнивать новые поступающие с каждым из них. Для 32-битного генератора это будет порядка 2^17 * 4 = 0.5 Мбайт, а вот для 64-битного, по аналогии, это будут уже гигабайты. Ну и время будет расти экспоненциально.
хотя у меня есть гипотеза на этот счёт
Поделитесь пожалуйста? Мне например кажется, что подобные тесты в вакууме — лажа.
В этом плане наука статистика очень хорошо отражает суть позитивизма в естественнонаучном принципе познания — нельзя доказать гипотезу, но можно попытаться её опровергнуть.
В нашем случае можно попытаться огромным числом различных способов найти неслучайность в выходе ГПСЧ и потерпеть неудачу, при этом зная, что это — именно ГПСЧ. Этим мы не докажем случайность последовательности, но и не опровергнем её. Когда, например, изменятся инструменты (новые алгоритмы, больше памяти, быстрее компы), доказательство неслучайности, может быть, и будет найдено, вот тогда можно будет сказать «ага!» и выкинуть конкретный алгоритм ГПСЧ на свалку.
Очень многие проблемы возникают как раз из-за непонимания этого основного принципа как статистики, так и строгой науки в целом.
Моя гипотеза, почему некоторые тесты из TestU01 стабильно не проходят, связана с особенностями эксперимента и организации кода. А именно, оригинальный фреймворк заточен (или это я только это в нём нашёл) на тестирование 32-битных (а точнее, int) генераторов. Хотя отдельный класс для тестирования 64-битных целых (а точнее long int) там есть, похоже, что он не очень отлажен — у меня падал с ошибками, которые я хоть и исправил, но не отладил до конца (если будут силы, свяжусь с автором и попрошу совета). Однако есть работающий класс для тестирования 64-битных чисел с плавающей запятой, к коим я и привёл выводы своих генераторов (к отрезку от 0.0 до 1.0). В double-ах всего 53 бита мантиссы, т.е. 11 бит исходного числа мы теряем. Вот здесь и лежит слабое место, и возможно, что тесты это «почувствовали».
В нашем случае можно попытаться огромным числом различных способов найти неслучайность в выходе ГПСЧ и потерпеть неудачу, при этом зная, что это — именно ГПСЧ. Этим мы не докажем случайность последовательности, но и не опровергнем её. Когда, например, изменятся инструменты (новые алгоритмы, больше памяти, быстрее компы), доказательство неслучайности, может быть, и будет найдено, вот тогда можно будет сказать «ага!» и выкинуть конкретный алгоритм ГПСЧ на свалку.
Очень многие проблемы возникают как раз из-за непонимания этого основного принципа как статистики, так и строгой науки в целом.
Моя гипотеза, почему некоторые тесты из TestU01 стабильно не проходят, связана с особенностями эксперимента и организации кода. А именно, оригинальный фреймворк заточен (или это я только это в нём нашёл) на тестирование 32-битных (а точнее, int) генераторов. Хотя отдельный класс для тестирования 64-битных целых (а точнее long int) там есть, похоже, что он не очень отлажен — у меня падал с ошибками, которые я хоть и исправил, но не отладил до конца (если будут силы, свяжусь с автором и попрошу совета). Однако есть работающий класс для тестирования 64-битных чисел с плавающей запятой, к коим я и привёл выводы своих генераторов (к отрезку от 0.0 до 1.0). В double-ах всего 53 бита мантиссы, т.е. 11 бит исходного числа мы теряем. Вот здесь и лежит слабое место, и возможно, что тесты это «почувствовали».
Sign up to leave a comment.
Случайные числа и детерминистичная симуляция