Последовательность двоичного входного файла для NIST

Question

Я разработал программу ГСЧ, а пока хочу проверить, случайны ли мои числа. Таким образом, я решил использовать NIST Test Suite.

Я все еще не понимаю формат входного файла, они говорят: "Пользователь может захотеть создать столько файлов произвольной длины, сколько пожелает. Файлы должны содержать двоичные последовательности, хранящиеся либо в виде символов ASCII, состоящих из нулей и единиц, либо в виде двоичных данных где каждый байт содержит восемь бит, состоящих из нулей и единиц "

Моя программа RNG на Python будет возвращать последовательность чисел построчно как:

69
11
68
55
33
20
75
96

Как я могу преобразовать их в подходящий входной файл для NIST?

Answer 1

Подходящим входом для NIST будет набор двоичных последовательностей. Вы можете просто преобразовать целые числа в двоичные числа, записать их в файл и использовать этот файл в качестве входных данных для программы NIST. Преобразование в двоичный формат и передача их в NIST не обязательно означает, что ваш ГСЧ пройдет там все тесты. Попробуем ответить на следующий вопрос.

Сколько битов вы производите для каждого целого числа?

Например, предположим, что ваш ГСЧ генерирует целые числа от 0 до 5 (равномерное распределение, все значения равновероятны). Поскольку для представления 5 потребуется как минимум 3 бита, мы будем использовать 3 бита для каждого целого числа.

0:000
1:001
2:010
3:011
4:100
5:101

Посмотрите на первый (самый значащий) бит для каждого из чисел. Четыре из них равны 0, а остальные два равны 1. Итак, всякий раз, когда вы выбираете случайное целое число от 0 до 5, вероятность того, что первый бит равен 0, выше, чем 1. Помните, что для ГСЧ нам нужно p(0)=p(1)=0,5 для каждого бита.

Теперь, если ГСЧ выдает значения от 0 до 7 (равномерно), мы могли бы преобразовать каждое из них в 3 бита и сохранить p(0)=p(1)=0,5 для всех индексов. Почему это? Поскольку у нас есть все 2³ разных значения (т. е. от 0 до 2³ -1), оно не сталкивается с какой-либо погрешностью ни по одному индексу (равное количество нулей и единиц).

Приведенное выше обсуждение приводит нас к выводу, что если у вас есть целые значения, выходящие из RNG, и они находятся в диапазоне от 0 до 2ⁿ-1, и каждое из них равновероятно, вы можете преобразовать их в n бит и соединить их для NIST. оценка. Если эти условия не выполняются (например, количество результатов не является степенью двойки), один из способов — установить максимальную степень двойки, которую можно разместить в выходном диапазоне вашего ГСЧ, и отбросить остальные значения..

Answer 2

Ваше первое случайное число - 69, то есть 1000101 в двоичном формате. Вы можете поместить это в свой тестовый файл как строку ASCII "1000101" или как семь битов в двоичный файл 1000101... Вариант ASCII, вероятно, проще, но размер файла будет в восемь раз больше. В любом случае вам, возможно, придется быть осторожным с ведущими нулями в двоичном формате, я не уверен, чего хочет NIST, не читая гораздо больше SP 800-22, чем у меня сейчас есть время.