Есть ли способ проверить качество PRNG для многомерного использования?

Question

Я занимаюсь оценкой некоторых PRNG, как с точки зрения скорости, так и качества. Одним из аспектов качества, который я хочу проверить, является многомерное распределение и предвзятость.

Я знаю батареи TestU01 и планирую использовать их (и, возможно, другие, которые предлагает NIST).

Но как насчет тестирования многомерного смещения? Boost's PRNG имеют некоторые комментарии, и Мерсэнн Твистер, как известно, является однородным в нескольких сот габаритах, в то время как Hellekalek PRNG имеет хорошее равномерное распределение в «нескольких» измерениях (как многие из них означают ...).

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

Есть ли известный способ тестирования PRNG для многомерного смещения? Я был бы в порядке, если тест ограничен 2, 3 или 4 измерениями; это было бы лучше, чем вообще никакого теста.

Answer 1

TestU01 хороший. PractRand, возможно, лучше (полное раскрытие: я написал PractRand). Для некоторых категорий PRNG RaBiGeTe также приличный. Существуют и другие варианты, которые не являются хорошими (NIST STS, Diehard и Dieharder хорошо известны, но неэффективны).

Любой хороший набор тестов будет проверять большое количество «измерений», хотя в принципе проще проводить всестороннее тестирование для более коротких корреляций в диапазоне, поэтому лучше работать на меньшем числе измерений.

Как правило, все, что проходит через батарею TestU01 BigCrush и/или один терабайт стандартной батареи PractRand, вероятно, будет хорошо для использования в некритическом режиме в реальном времени. Однако такой тип тестирования не может идентифицировать некоторые категории проблем, в частности, проблемы корреляции между семенами.