Линейная рекуррентная последовательность максимального периода

Определение 6.9. Если минимальный период линейной рекуррентной последовательности над полем F_q с ненулевым начальным состоянием и неприводимым характеристическим многочленом f (x), /о ф 0, deg/(ж) = гп, равен q^m — 1, то последовательность называется линейной рекуррентной последовательностью максимального периода.

Из теоремы 6.1 получаем следующие утверждения.

Следствие 1. Пусть над полем F_f/ задана линейная рекуррентная последовательность с неприводимым характеристическим многочленом f (x), /о Ф 0, deg f (x) = т. Тогда минимальный период данной последовательности является делителем числа q^m — 1.

Следствие 2. Линейная рекуррентная последовательность над полем F_f/ обладает максимальным периодом в том и только том случае, когда ее характеристический многочлен примитивен.

Теорема 6.2. Пусть f (x) € F_q[x, /о ф 0, deg/(ж) = т — характеристический многочлен линейной рекуррентной последовательности с начальным состоянием Щ. Минимальный многочлен т (х) данной последовательности совпадает с f (x) в том и только том случае, если векторы состояний щ, й,… ,%_n-i линейно независимы.

Доказательство. Пусть для некоторого t вектор щ есть линейная комбинация векторов … , щ~.

Умножая обе части данного равенства на А^п, где А — сопровождающая матрица, получим.

т.е. многочлен d (x) = x^l — dt-х¹~¹——-dx — do является характеристическим многочленом для рассматриваемой линейной рекуррентной последовательности.

Значит, при линейной независимости векторов ио, Щ,… степень любого характеристического многочлена не может быть меньше, чем га. С учетом утверждения 6.7 отсюда следует, что т (х) = f (x). Тем самым в одну сторону теорема доказана.

Пусть теперь т (х) = f (x). Предположим, что векторы начальных состояний Uo, tZi, … , v,_m- являются линейно зависимыми. Тогда для некоторого t ^ га — 1 будет выполнено равенство.

при некоторых do,…, d_t-i? F^, из которого следует, что многочлен.

степень которого не превосходит га — 1, является характеристическим многочленом для рассматриваемой линейной рекуррентной последовательности. Отсюда.

Полученное противоречие и завершает доказательство. ?

Из доказательства теоремы следует, что минимальным многочленом соответствующей линейной рекуррентной последовательности является многочлен.

заданный соотношением.

при минимально возможном натуральном t.

Следствие 1. Пусть линейная рекуррентная последовательность задана характеристическим многочленом f (x) и начальным состоянием Щ = (0,0,…, 0,1). Тогда ее минимальный многочлен совпадает с f{x).