Последовательность элементов s0, s1,… поля Fq, удовлетворяющих условию
sn+k = ak-1sn+k-1 + ak-2sn+k-2 + …+ a0sk , (3.3.1)
где ak-1,ak-2,…a0 – фиксированные элементы поля, называется линейной рекуррентой (ЛРП) k-го порядка над полем Fq. Эта последовательность полностью определяется вектором начального состояния S0= (s0,s1,…,sk-1) и коэффициентами ak-1,ak-2,…a0.
С линейной рекуррентой можно связать матрицу
Рассмотрим теперь последующие состояния ЛРП S1=(s1, s2,…,sk), S2=(s2,s3,…,sk+1),… Определение (3.3.1) можно переписать в виде
Si= Si-1A, i=l, 2,… (3.3.2)
Далее рассматриваются лишь ЛРП с условием a0¹0. В этом случае матрица А является элементом группы GL(k,Fq) всех невырожденных матриц k-го порядка с элементами из поля Fq. Поскольку эта группа конечна, то матрица А имеет конечный порядок как элемент группы.
Теорема 1. Любая линейная рекуррента при a0¹0 является чисто периодической последовательностью.
