Означення. Анулюючим многочленом послідовності , називається такий многочлен над полем , що , де – нульова послідовність.
Означення. Мінімальним многочленомпослідовності , називається нормований анулюючий многочлен найменшого степеня.
Мінімальним многочленом рекурентної послідовності над полем є многочлен
,
який є мінімальним многочленом матриці , оскільки вона для цього многочлену є супроводжуючою. За побудовою, для кожного такту роботи РЗЛЗЗ він задає співвідношення
,
або
, де .
Початковий стан рекуренти складається з елементів.
Приклад. Мінімальним многочленом рекурентної послідовності з рекурентним співвідношенням буде многочлен
або
.
Покажемо, що для нашої рекуренти існують інші рекурентні співвідношення.
Розглянемо многочлен виду і побудуємо для нього супроводжуючу матрицю, порядок якої дорівнює . Тоді коефіцієнти многочлена задають для деякої рекуренти співвідношення виду
або
.
Коефіцієнти можна легко отримати за правилами добутку многочленів , за якими набір коефіцієнтів многочлена зсувається на величину степеня кожного одночлену , що входить до , а потім ці зсуви виду підсумовуються. Таким чином, вектор коефіцієнтів дорівнює сумі деяких таких зсувів.
Многочлени виду називаються похідними, або покриваючими многочленами рекурентної послідовності з мінімальним многочленом .
Застосуємо до нашої рекуренти рекурентне співвідношення з коефіцієнтами . Рекурента задовольняє співвідношенню для довільного зсуву, а це значить, що вона буде задовольняти рекурентне співвідношення з коефіцієнтами .
Нехай тепер задані дві рекурентні послідовності з відомими рекурентними співвідношеннями (мінімальними многочленами , ) і початковими станами і , розмірності яких задовольняють умову .
Рекурентне співвідношення для суми цих рекурент задають коефіцієнти многочлена , тому що цей многочлен є покриваючим для кожної з рекурент. Тому довжина (розмірність) початкового стану дорівнює .
Якщо ми продовжимо і , за відповідними рекурентними законами до бітів, то отримаємо послідовності і , з яких отримаємо .
Як нам відомо, для того, щоб послідовність векторів , , мала максимальний період , слід вибирати мінімальний многочлен примітивним многочленом степеня над полем . Тому будемо вважати многочлен примітивним.
У цьому випадку послідовність , при пробігає всі ненульові двійкові вектори, тобто довільний вектор дорівнює вектору при деякому .
Виберемо в матриці , рядками якої є рекуренти два ненульових нерівних вектори , і обчислимо вектор . За попереднім, існує ціле , таке, що .
При цьому
, ,
звідки
і .
Таким чином, для нашої рекуренти виконується тричленне співвідношення