3.3.10. Линейные рекуррентные последовательности

Последовательность элементов s₀, s₁,… поля F_q, удовлетворяющих условию

s_n+k = a_k-1s_n+k-1 + a_k-2s_n+k-2 + …+ a₀s_k , (3.3.1)

где a_k-1,a_k-2,…a₀ – фиксированные элементы поля, называется линейной рекуррентой (ЛРП) k-го порядка над полем F_q. Эта последовательность полностью определяется вектором начального состояния S₀= (s₀,s₁,…,s_k-1) и коэффициентами a_k-1,a_k-2,…a₀.

С линейной рекуррентой можно связать матрицу

Рассмотрим теперь последующие состояния ЛРП S₁=(s₁, s₂,…,s_k), S₂=(s₂,s₃,…,s_k+1),… Определение (3.3.1) можно переписать в виде

S_i= S_i-1A, i=l, 2,… (3.3.2)

Далее рассматриваются лишь ЛРП с условием a₀0. В этом случае матрица А является элементом группы GL(k,F_q) всех невырожденных матриц k-го по­рядка с элементами из поля F_q. Поскольку эта группа конечна, то матрица А имеет конечный порядок как элемент группы.

Теорема 1. Любая линейная рекуррента при a₀0 является чисто пе­риодической последовательностью.