Pull to refresh

Comments 21

Позволяют ли результаты этих тестов говорить о том, какая именно связь существует внутри последовательности?
Конечно, каждый тест заточен на поиск определённой взаимосвязи.
Про «o6hb8qgkbkcupvhag42astgqcruzkmgmxkry2q8u17r5g5r2v7» что-нибудь скажут тесты? Алгоритм получения такой последовательности известен, интересно что скажут другие методы про него…
На сайте Ниста она выкладывают исходники этих всех тестов. Скачайте и прогоните через тесты ))
Тесты мне покажут какие-то «странные» цифры. Даже скажут что последовательность неслучайная, но как эти результаты использовать для определения алгоритма создания последовательности?
Вопрос интересный Получается так, что если тест пройден, то об алогритме ничего сказать и нельзя! А если НЕ пройден, то уже можно строить догадки. Например если тест на LFSR показал плохой результат, то в алгоритме скорее всего затесался регистр сдвига. Или если не прошёл спектральный тест, то наложились некие пероидические сигналы.
Спасибо за интрепретацию! Наиболее интересный вопрос — понять какой генератор использовался: линейный конгруэнтный, Type3 или вообще Mersenne. Правда, гипотеза о LC-RNG проверяется за несколько часов для самых распространенных.
Спасибо, интересно.
Не понял какая связь между P-значением и вероятность ошибки первого рода. Почему P-значение сравнивают именно с α? Можете прояснить этот момент?
И почему альфа выбирается такой маленькой. Т.е. если P-значение равно всего 0.02, то последовательность все-равно считается случайной несмотря на такую низкую вероятность?

И еще одно у вас в тексте написано:
В дальнейшем P-значение сравнивается с α, и если она меньше α, то нулевая гипотеза принимается и последовательность признается случайной.

это опечатка, и следует читать «и если она больше α»?
И отвечаю по P-значениям. Alpha — это как бы «уровень строгости». Чем оно меньше, тем «сложнее» последовательностям проходить тесты, но уж если тест пройден, то с более высоким уровнем доверия.
Вот это вот меня как раз и смущает.
Если мы задаем такой низкий уровень строгости, то по элементарной логике (возможно ложной) создается впечатление, что 99 последовательностей из 100 пройдут тест.
Интуитивно просто кажется, что такое маленькое значение было бы оправдано, если бы последовательность принималась в случае если P<α, а не наоборот.

И поэтому я так понял, что тесты отбраковывают только самые очевидно неправильные последовательности, пропуская остальные. Это так? Или все-таки там какой-то подвох в матане?
А, понял причину вашего смущения. Попробую пояснить. Пример: взяли α = 0.001. Это всего лишь означает, что из 1000 последовательностей мы готовы незаслуженно отбраковать одну. (Та самая ошибка первого рода). Это конечно же не означает, что из этих 1000 мы заапрувим 999. В криптографии обычно берут 0.001 < α < 0.01.
Вопрос. А в чем состоит проблема создания аппаратного генератора? Смесь шумящего микрофона, дребезжащего контакта, сканера радиочастот и света на Марсе. Все перемешать в равномерную кашу. Правда интересно.
Проблема в предсказуемости. Ваш микрофон может шуметь похожим образом с микрофоном вашего соседа. Или они узнают, какая у вас аудиокарта, купят такую же, и будут развлекаться )). Свет на марсе и радиоэфир более или менее одинаков для группы людей.

Наиболее реально, это всяческие шумящие диоды и их лавинные пробои. Вот они дают «кошерные» числа. Например как тут: holdenc.altervista.org/avalanche/
Вопрос в тему. Раньше была ещё батарея тестов Diehard, кто какие ещё знает?
Diehard и сейчас есть. Есть ещё Dieharder. Есть тесты от NIST, о которых эта статья. Я в своей статье проверял свои же велосипеды, а также аппаратный RDRAND с помощью TestU01.
Хорошая статья. В свое время обнаружил, что случайные последовательности можно проверять на степень сжимаемости с помощью стандартных архиваторов, я использовал 7zip с LZMA.
Есть исходники, может кому интересно будет: Random-Sequence-Analysis (также там реализованы другие простые тесты).

P.S. На хабре все-таки не хватает поддержки либы для отрисовки математических формул, например MathJax. Представляю, как могло быть муторно делать все это в виде картинок.
Не всё так плохо )
pdflatex в купе с convert -trim
Использую данные тесты для тестирования большого объема данных в качестве дополнительной методики.
Для тех кто, решит использовать этот пакет:
1. Программные коды представленные на сайте NIST далеко не оптимальны по скорости и памяти. Лучше реализовать самостоятельно.
В моем случае ускорение измеряется десятками раз. Для меня это критично, ибо объемы данных у меня таковы, что их реализацией будет считаться около двух лет, а мой оптимизированный вариант считает 1-2 недели. Думаю разница очевидна.
Причем ускорение достигается элементарными оптимизациями кода.
2. некоторые тесты содержат ошибки (в реализации на сайте ниста). То есть если ваши последовательности не проходят тест, не спешите с выводами — проверьте реализацию.
3. Там для вычисления вероятностей значимости в некоторых тестах используется функция igamc. Сравнивал полученные значения с данными Maple — погрешность составляла до 0,1. Последний факт сильно искажает результаты тестирования, распределение вероятностей значимости не проходит проверку на равномерность.
4. Поищите дополнительные публикации. Например, тест преобразования Фурье с ростом длины последовательностей начинает давать ошибку (так как реальное распределение статистик начинает отличаться от используемого приближения)

Only those users with full accounts are able to leave comments. Log in, please.