Коды и шифры

М11. Двоичные линейные рекурренты

Как и можно было бы предположить после анализа чисел Фибоначчи и аналогичных им последовательностей, нам необходимо исследовать свойства многочлена степени k, сопоставленного линейной рекурренте степени k. Общий вид подобной рекурренты таков:

U_n = a₁U₍_n_-1) + a₂U₍_n_-2) + ...+ a_kU₍_n_-_k₎,

а ассоциированный с ней многочлен выглядит так:

X^k + a₁X^k^-1 + ... +a_k = 0.

Напомним, что все вычисления выполняются по модулю 2, так что -a_s - это то же самое, что +a_s. Поскольку рекуррента является двоичной и имеет степень k, то все ее коэффициенты (или множители) равны либо 0, либо 1, и, более того, последний коэффициент, a_k, можно положить равным 1. Поэтому существует 2⁽^k^-1) различных наборов коэффициентов.

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

Теорема

Пусть (n) обозначает количество натуральных чисел, меньших n и не имеющих с n общих делителей. Тогда число двоичных линейных рекуррент степени k, порождающих последовательности знаков гаммы максимального периода 2^k-1, равно

Функция (n) называется -функцией Эйлера (произносится "фи"). Ее очень просто вычислить. Пусть p₁, p₂, ..., p_r - все различные простые числа, такие что n делится без остатка на некоторую степень каждого из них. Тогда

Так, например, для k=12 получаем

2¹²-1=4095=335713,

и поэтому

(4095)= =1728.

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

=144,

что и утверждается в главе 8. Заметим, что хотя 4095 делится на 3², соответствующая дробь, входящая в функцию Эйлера, равна двум третям, а не восьми девятым.

Аналогично, для k=23 число двоичных линейных рекуррент степени23, порождающих двоичные последовательности максимального периода (2²³-1), равно

то есть

причем и 47, и 178481 - простые числа. То, что число 178481 является простым, следует из того, что оно не делится ни на одно простое число, меньшее своего квадратного корня, т.е. ни на одно простое число, меньшее 422. Итак, получаем, что число таких последовательностей равно

=356960,

о чем также сказано в главе 8.

(Доказательство приведенной теоремы можно найти в [8.2]).

Содержание