Comments 21
Позволяют ли результаты этих тестов говорить о том, какая именно связь существует внутри последовательности?
Конечно, каждый тест заточен на поиск определённой взаимосвязи.
Про «o6hb8qgkbkcupvhag42astgqcruzkmgmxkry2q8u17r5g5r2v7» что-нибудь скажут тесты? Алгоритм получения такой последовательности известен, интересно что скажут другие методы про него…
На сайте Ниста она выкладывают исходники этих всех тестов. Скачайте и прогоните через тесты ))
Тесты мне покажут какие-то «странные» цифры. Даже скажут что последовательность неслучайная, но как эти результаты использовать для определения алгоритма создания последовательности?
Вопрос интересный Получается так, что если тест пройден, то об алогритме ничего сказать и нельзя! А если НЕ пройден, то уже можно строить догадки. Например если тест на LFSR показал плохой результат, то в алгоритме скорее всего затесался регистр сдвига. Или если не прошёл спектральный тест, то наложились некие пероидические сигналы.
Спасибо, интересно.
Не понял какая связь между P-значением и вероятность ошибки первого рода. Почему P-значение сравнивают именно с α? Можете прояснить этот момент?
И почему альфа выбирается такой маленькой. Т.е. если P-значение равно всего 0.02, то последовательность все-равно считается случайной несмотря на такую низкую вероятность?
И еще одно у вас в тексте написано:
это опечатка, и следует читать «и если она больше α»?
Не понял какая связь между P-значением и вероятность ошибки первого рода. Почему P-значение сравнивают именно с α? Можете прояснить этот момент?
И почему альфа выбирается такой маленькой. Т.е. если P-значение равно всего 0.02, то последовательность все-равно считается случайной несмотря на такую низкую вероятность?
И еще одно у вас в тексте написано:
В дальнейшем P-значение сравнивается с α, и если она меньше α, то нулевая гипотеза принимается и последовательность признается случайной.
это опечатка, и следует читать «и если она больше α»?
Злобная опечатка! Поправил, спс.
И отвечаю по P-значениям. Alpha — это как бы «уровень строгости». Чем оно меньше, тем «сложнее» последовательностям проходить тесты, но уж если тест пройден, то с более высоким уровнем доверия.
Вот это вот меня как раз и смущает.
Если мы задаем такой низкий уровень строгости, то по элементарной логике (возможно ложной) создается впечатление, что 99 последовательностей из 100 пройдут тест.
Интуитивно просто кажется, что такое маленькое значение было бы оправдано, если бы последовательность принималась в случае если P<α, а не наоборот.
И поэтому я так понял, что тесты отбраковывают только самые очевидно неправильные последовательности, пропуская остальные. Это так? Или все-таки там какой-то подвох в матане?
Если мы задаем такой низкий уровень строгости, то по элементарной логике (возможно ложной) создается впечатление, что 99 последовательностей из 100 пройдут тест.
Интуитивно просто кажется, что такое маленькое значение было бы оправдано, если бы последовательность принималась в случае если P<α, а не наоборот.
И поэтому я так понял, что тесты отбраковывают только самые очевидно неправильные последовательности, пропуская остальные. Это так? Или все-таки там какой-то подвох в матане?
А, понял причину вашего смущения. Попробую пояснить. Пример: взяли α = 0.001. Это всего лишь означает, что из 1000 последовательностей мы готовы незаслуженно отбраковать одну. (Та самая ошибка первого рода). Это конечно же не означает, что из этих 1000 мы заапрувим 999. В криптографии обычно берут 0.001 < α < 0.01.
Вопрос. А в чем состоит проблема создания аппаратного генератора? Смесь шумящего микрофона, дребезжащего контакта, сканера радиочастот и света на Марсе. Все перемешать в равномерную кашу. Правда интересно.
Чтоб убедиться что с вашей конструкцией не случится вот это
В скорости.
Поток у аппаратных генераторов, как правило, хилый
Поток у аппаратных генераторов, как правило, хилый
Проблема в предсказуемости. Ваш микрофон может шуметь похожим образом с микрофоном вашего соседа. Или они узнают, какая у вас аудиокарта, купят такую же, и будут развлекаться )). Свет на марсе и радиоэфир более или менее одинаков для группы людей.
Наиболее реально, это всяческие шумящие диоды и их лавинные пробои. Вот они дают «кошерные» числа. Например как тут: holdenc.altervista.org/avalanche/
Наиболее реально, это всяческие шумящие диоды и их лавинные пробои. Вот они дают «кошерные» числа. Например как тут: holdenc.altervista.org/avalanche/
Вопрос в тему. Раньше была ещё батарея тестов Diehard, кто какие ещё знает?
Хорошая статья. В свое время обнаружил, что случайные последовательности можно проверять на степень сжимаемости с помощью стандартных архиваторов, я использовал 7zip с LZMA.
Есть исходники, может кому интересно будет: Random-Sequence-Analysis (также там реализованы другие простые тесты).
P.S. На хабре все-таки не хватает поддержки либы для отрисовки математических формул, например MathJax. Представляю, как могло быть муторно делать все это в виде картинок.
Есть исходники, может кому интересно будет: Random-Sequence-Analysis (также там реализованы другие простые тесты).
P.S. На хабре все-таки не хватает поддержки либы для отрисовки математических формул, например MathJax. Представляю, как могло быть муторно делать все это в виде картинок.
Использую данные тесты для тестирования большого объема данных в качестве дополнительной методики.
Для тех кто, решит использовать этот пакет:
1. Программные коды представленные на сайте NIST далеко не оптимальны по скорости и памяти. Лучше реализовать самостоятельно.
В моем случае ускорение измеряется десятками раз. Для меня это критично, ибо объемы данных у меня таковы, что их реализацией будет считаться около двух лет, а мой оптимизированный вариант считает 1-2 недели. Думаю разница очевидна.
Причем ускорение достигается элементарными оптимизациями кода.
2. некоторые тесты содержат ошибки (в реализации на сайте ниста). То есть если ваши последовательности не проходят тест, не спешите с выводами — проверьте реализацию.
3. Там для вычисления вероятностей значимости в некоторых тестах используется функция igamc. Сравнивал полученные значения с данными Maple — погрешность составляла до 0,1. Последний факт сильно искажает результаты тестирования, распределение вероятностей значимости не проходит проверку на равномерность.
4. Поищите дополнительные публикации. Например, тест преобразования Фурье с ростом длины последовательностей начинает давать ошибку (так как реальное распределение статистик начинает отличаться от используемого приближения)
Для тех кто, решит использовать этот пакет:
1. Программные коды представленные на сайте NIST далеко не оптимальны по скорости и памяти. Лучше реализовать самостоятельно.
В моем случае ускорение измеряется десятками раз. Для меня это критично, ибо объемы данных у меня таковы, что их реализацией будет считаться около двух лет, а мой оптимизированный вариант считает 1-2 недели. Думаю разница очевидна.
Причем ускорение достигается элементарными оптимизациями кода.
2. некоторые тесты содержат ошибки (в реализации на сайте ниста). То есть если ваши последовательности не проходят тест, не спешите с выводами — проверьте реализацию.
3. Там для вычисления вероятностей значимости в некоторых тестах используется функция igamc. Сравнивал полученные значения с данными Maple — погрешность составляла до 0,1. Последний факт сильно искажает результаты тестирования, распределение вероятностей значимости не проходит проверку на равномерность.
4. Поищите дополнительные публикации. Например, тест преобразования Фурье с ростом длины последовательностей начинает давать ошибку (так как реальное распределение статистик начинает отличаться от используемого приближения)
Sign up to leave a comment.
Статистическая проверка случайности двоичных последовательностей методами NIST