Минимальный многочлен последовательности

Любая линейная рекуррентная последовательность, очевидно, обладает множеством различных рекуррентных соотношений типа.

(6.2). В этой связи мы можем ввести следующее определение.

Определение 6.6. Пусть линейная рекуррентная последовательность щ, щ,… определена равенством (6.2), а ее характеристический многочлен удовлетворяет равенству (6.3).

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

ио, щ,____Степень минимального многочлена называется линейной

сложностью данной последовательности.

Минимальный многочлен последовательиости_у состоящей из одних нулей, полагается равным 1.

Таким образом, линейная сложность последовательности uo, ui,… определяет минимальную длину линейного регистра сдвига, реализующего данную последовательность.

Утверждение 6.7. Любой характеристический многочлен линейной рекуррентной последовательности кратен минимальному многочлену.

Доказательство. Предположим, что для некоторой линейной рекуррентной последовательности характеристический многочлен f (x) не делится без остатка на минимальный многочлен т (х). Тогда в результате деления с остатком получим.

Обозначим а коэффициент при старшем члене многочлена г (х) и рассмотрим многочлен ri (x) = a~¹(f (x) — d (x)m (x)). Тогда, из утверждения 6.6 получаем, что многочлен ri (x) также является аннулирующим многочленом и, следовательно, характеристическим многочленом. Поскольку degri (rc) < degra (x), получаем противоречие с тем, что многочлен т (х) является минимальным многочленом. ?

Следствие 1. Пусть над полем F_q задана линейная рекуррентная последовательность с характеристическим многочленом f (x), /о ф 0. Если многочлен f (x) неприводим над полем F_q, то минимальный многочлен данной линейной рекуррентной последовательности совпадает с f (x).

Определение 6.7. Пусть гп (х) = Y^j=o^mj^x^ ^ И «отличный от нуля многочлен. Если то ф 0, то наименьшее натуральное число е такое, что многочлен т (х) делит многочлен х^е — 1, называется периодом, порядком или экспонентой многочлена т (х) и обозначается о; (га).

Если же то = 0, то многочлен т{х) однозначно представим в виде т (х) = x^hg{x), где h е N, g{x) е F₉[ar], до ф 0. В этом случае под периодом многочлена т (х) понимаем со (д).

Упражнение 6.1.3. Пусть f (x) € F_g[x], deg/(ж) = m ^ 1, /о Ф 0. Докажите, что существует натуральное е ^ q^m — 1, при котором.

Известно, см. [3], что период неприводимого многочлена f (x) над полем ?_ч степени т является делителем числа q^m — 1.

Определение 6.8. Неприводимый многочлен f (x) е F_f/[ж], /о ф 0, степени т ^ 1 называется примитивным многочленом над полем IF_f/, если его период равен q^m — 1.

Напомним, что в общем случае период неприводимого многочлена степени гп над полем F_(/ является делителем числа q^m — 1. Отсюда следует, если число q^m — 1 простое, то любой неприводимый многочлен степени т над полем F_f/ будет примитивным. Общее число примитивных многочленов степени т > 1 над полем F_f; равно q^m — 1). Построение примитивных многочленов в общем случае представляет сложную задачу. Вместе с тем при известном разложении числа q^m — 1 на простые множители задача проверки примитивности заданного неприводимого многочлена допускает эффективное решение.

Утверждение 6.8 (см. [3]). Пусть f (x) — неприводимый многочлен степени т над полем ?,_г Многочлен f (x) является примитивным в том и только том случае, если для любого простого числа р, делящего q^m — 1, выполнено неравенство

Теорема 6.1. Пусть т (х) е F₉[x], mo ф 0 — минимальный многочлен линейной рекуррентной последовательности uq, щ,…, определенной над полем ?_ч. Тогда минимальный период линейной рекуррентной последовательности равен периоду си (т) многочлена т (х).

Доказательство. Пусть т — минимальный период линейной рекуррентной последовательности. Тогда f (x) = х^т — 1 является характеристическим многочленом этой последовательности и, с учетом утверждения 6.7,

Отсюда следует, что т кратно периоду и>(гп) многочлена rn (x). С другой стороны, из равенства.

следует, что oj (m) является периодом линейной рекуррентной последовательности, т. е. ш (т) кратно т. ?

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

Утверждение 6.9. Пусть многочлен /(ж) е F_f/[ж] удовлетворяет равенству /(ж) = fi{x)f‘₂(x)? ?? ft (x) и НОД (/i, fj) = 1 для i ф j. Тогда период многочлена /(ж) равен наименьшему общему кратному периодов многочленов fi (x),… ft (x).

Пример 6.1. Надо найти период многочлена f (x) — х² + 1 € Рз[ж]. Непосредственной проверкой убеждаемся в том, что многочлен /(ж) не имеет корней в поле F3 = {0,1,2}, следовательно, он неприводим над данным полем. В таком случае период многочлена /(ж) будет делителем числа З² — 1 = 8 ненулевых элементов поля F32 — Тз[ж]/ж² + 1. Далее непосредственной проверкой получаем:

Таким образом, период данного многочлена равен 4.

Далее надо найти период многочлена /(ж) = ж⁵ + ж + 1 в поле F‘2[ж]. Легко проверить, что разложение многочлена /(ж) в поле F2 на неприводимые множители имеет вид:

следовательно, период многочлена /(ж) = ж⁵ + ж+1 равен наименьшему общему кратному периодов его множителей:

Также для нахождения периода можно использовать следующее утверждение.

Утверждение 6.10. Пусть /(ж) = д{х)т (х) € Р₉[ж], где д (ж) — неприводимый многочлен и q = р^п, р — простое число, до ф 0. Тогда периоды многочленов /(ж) и д (х) связаны равенством

где t — наименьшее натуральное число, при котором р¹ ф т.

Пример 6.2. Необходимо найти период многочлена

Многочлены х² + х + 1 и ж³ + х² + 1 являются неприводимыми, и их периоды равны соответственно 3 и 7. Далее, наименьшее целое t такое, что 2^l ^ тах{10,20}, равно t = 5. Отсюда.

Упражнение 6.1.4. Для многочлена через /*(ж) обозначим многочлен.

Докажите, что периоды многочленов f (x) и /*(ж) совпадают. Указание: покажите, что равенство х^г -1 = f (x)k (x) выполняется в том и только том случае, если верно равенство х^г — 1 = —f*(x)k*(x).