Линейные рекурренты

Рассмотренные выше последовательности являются примерами последовательностей, полученных с помощью так называемых линейных рекуррентных соотношений. Поскольку получение очередного элемента данных последовательностей связано со сложением величин, кратных значениям двух предыдущих элементов, то они, точнее говоря, являются линейными рекуррентными последовательностями степени 2. И вообще, в линейной рекуррентной последовательности k-й степени каждый следующий элемент является суммой чисел, кратных k предыдущим элементам. Так, например, если через U_n обозначить n-й элемент последовательности, то соотношение

U_n = U_(n-1) + 2 U_(n-2) - U_(n-3)

является линейным рекуррентным соотношением степени 3, а

U_n = U_(n-3) + U_(n-5)

является линейным рекуррентным соотношением степени 5. То, что во втором случае некоторые из пяти предыдущих элементов в соотношение не входят, значения не имеет: для вычисления элемента последовательности требуется пять предыдущих элементов, но три из них, U_(n-1), U_(n-2) и U_(n-4) входят в соотношение с коэффициентом 0. Однако, если бы элемент U_(n-5) не входил в соотношение, то оно уже не было бы соотношением 5-й степени. В нашем случае все коэффициенты - целые числа, они могут быть и положительными, и отрицательными, и нулевыми. Предполагается, что в линейном рекуррентном соотношении степени k элемент U_(n-k) всегда присутствует с положительным или отрицательным, но только не нулевым коэффициентом.

Порядок элементов линейных рекуррентных последовательностей, как правило, растет очень быстро, и хотя у них есть интересные арифметические свойства, использовать их для криптографических целей можно только после замены значений элементов на остатки от их деления по модулю 2. То есть, элемент заменяется на 0, если значение четное, и на 1, если оно нечетное. Таким образом, получается двоичная последовательность. Вычислять элементы линейной рекурренты по модулю 2 особенно просто. Совсем не нужно сначала вычислять действительное значение элементов, а затем уже заменять их нулем или единицей. Каждое слагаемое просто заменяется на 0 или 1 в момент вычисления; затем остается только сложить несколько нулей и единиц, что гораздо проще, нежели суммировать постоянно растущие целые числа. В результате получается та же самая двоичная последовательность, как если бы мы вычисляли значение каждого элемента, а уже затем заменяли его на 0 или на 1. Так, например, линейная рекуррента степени 2

U_n = 3U_(n-1) -2 U_(n-2)

с начальными значениями U₀=0, U₁=1 выглядит так:

0, 1, 3, 7, 15, 31, 63, 127, 255, 511,....

Если в момент вычисления заменить каждый элемент его остатком по модулю 2, получится двоичный эквивалент этой последовательности:

0, 1, 1, 1 ,1 ,1 ,1 ,1 ,1 ,1,....

что, без сомнения, справедливо, так как

U_n = 2ⁿ-1,

и поэтому все элементы последовательности, кроме U₀, нечетные.

Ясно, что эта конкретная последовательность для криптографии бесполезна в силу своей исключительной неравновероятности. Допустим, однако, что какие-то линейные двоичные последовательности нам подходят. Как их можно было бы использовать? Сначала рассмотрим практическую задачу использования последовательности двоичных знаков гаммы для шифрования.