Получение псевдослучайных чисел на основе полиномиального счетчика (сдвигового регистра)

В основе этого алгоритма, лежит операция исключающего ИЛИ (сумма по модулю два). Таблица истинности для данной функции выглядит следующим образом:

Схемы, представленные на рисунке ниже, являются простейшими полиномиальными счётчиками. Нулевой бит в таких схемах вычисляется на основе функции исключающего ИЛИ, а все остальные биты получаются простым сдвигом. Разряды с которых сигнал идёт на исключающее ИЛИ называются отводами.

Рассмотрим, как будут изменяться значения в этих регистрах при начальном значении 001:

Оба регистра начинают работу с одного и того же значения, но потом значения, генерируемые регистрами начинают быстро расходиться. Но через 6 шагов, оба регистра возвращаются в исходное состояние.

Легко показать, что оба этих регистра сгенерировали максимально длинную последовательность, которая содержит все комбинации, кроме нулевой. Т.е. при разрядности регистра m, можно получить последовательность длинной 2^m-1.

Полиномиальный счётчик любой разрядности имеет ряд комбинаций отводов, которые обеспечат последовательность максимальной длины, использование неверных комбинаций приведёт к генерации коротких последовательностей. Отдельная и довольно сложная задача – поиск этих комбинаций отводов.

Стоит заметить, что эти комбинации не всегда уникальны. К примеру, для 10-битного счётчика их существует две: [6;9] и [2;9], для шестиразрядного счётчика таких комбинаций двадцать восемь.

Для того, чтобы найти эти комбинации, необходимо представить счётчик в виде полинома. Счётчики из примера будут иметь следующий вид: x² XOR 1 и x² XOR x XOR 1.

Из теории известно, что необходимым и достаточным условием генерации полной последовательности является примитивность характеристического полинома. Это значит, что:

Характеристический полином нельзя представить в виде произведения полиномов более низкой степени;

Характеристический полином является делителем полинома z^δ XOR 1, при(δ=2^m-1, и не является делителем при любых других значениях δ<2^m-1.

Преимуществами полиномиального счётчика является простота, как программной, так и аппаратной реализации, скорость работы и криптографическая стойкость.