Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
многочлена вида хе - 1 ии для какого 0 < ё < <21. Таким образом, ord (А
(х)) ^ 21. Импульсная функция, соответствующая данному рекуррентному
соотношению, имеет вид
0.0. 0, 0, 1,0, КО, 0. 1,0,0, С I, 0, 0, 1.0, I, 1,0,0, 0,0,0, 1, ....
Как и должно быть, эта последовательность периодична с минимальным
периодом г - 21. Если в качестве вектора начального состояния взять
вектор (0. 0, 0, 0, 1, 1), то мы получим бинарную последовательность
0, о.о. 1, 1, 1, 1,0, 1.1.0, 1,0, 1.0, 1, I. 1.0, 1,0. 0.0,0, 1,1.
с минимальным периодом г - 21. Если же в качестве вектора начального
состояния взять вектор (0, 0, 0, 1, 0, 0), то мы получим бинарную
последовательность
°-0. о, 1, 0,0, О, 1, 1,0, 1, I. 1. 1, 1, 1.0.0, 1, 1, 1,0, 0.0. 1,0,
о,... ,
514
Гл. 8. Линейные рекуррентные последовательности
. г;.
также имеющую минимальный период 21. При этом каждый ненулевых 6*мерных
векторов над полем Р2 появляется в каче вектора состояния в точности в
одной нз этих трех послед(c) тельностей. Еслн в качестве вектора начального
состояния вз любой ненулевой вектор, то мы получим рекуррентную поел
вательность, имеющую минимальный период, равный 21, и сов дающую с
точностью до сдвига с одной из трех полученных в последовательностей.
8.31. Пример. Если многочлен / (х) (j [х] степени k it водим, то его
порядок ord (/ (х)) не обязательно делит числоqk - Чтобы показать это,
рассмотрим, например, многочлен } (х) - ха 4- х f 1 ? Г3 [х]. Этот
многочлен приводим, так как
/ (х) --- х6 4- х -г 1 = (xs + х2 -- 1) (х- -• х - !}.
Из теоремы 8.27 и примера 8.14 следует, что ord (f (х)) равен и не
является делителем числа 25 - 1 31.
Для приложений особый интерес представляют лииейн: рекуррентные
последовательности, имеющие очень большой нимальный период. Из теоремы
8.7 известно, что для одиород! линейной рекуррентной последовательности
k-rо порядка полем F? минимальный период не может превышать qk Для того
чтобы построить рекуррентную последовательно! минимальный период которой
в точности равен qk - 1, воспой зуемся понятием примитивного многочлена
(см. определение ЗЛ
8.32. Определение. Однородная линейная рекуррентная следовательность иад
полем характеристический миогоч которой является примитивным многочленом
над полем а вектор начального состояния - ненулевым вектором, на вается
последовательностью максимального периода над полем
8.33. Теорема. Каждая последовательность k-го порядка максимального
периода над полем является чисто периода ской последовательностью, а ее
минимальный период равняв
q* _
W.
Пг
М
'уХ-Р,
• Д
У*
1, наибольшему из возможных значений, которое мо, принимать минимальный
период однородной линейной рекуррет ной последовательности k-го порядка
над полем
Доказательство. Тот факт, что рассматриваемая последо: тельность является
чисто периодической иоследовательност) минимальный период которой равен
qk- I, есть следствие рем 8.28 и 3.16. Остальное легко вытекает из
теоремы 8.7.
8.34. Пример. Характеристическим многочленом рассмот] ного в примере 8.2
линейного рекуррентного соотношения полем Fа
§ 3. Производящие функции 515
является многочлен f (х) = х7 - х4 -- х3 - х2 - I ? М* Так
как / (х) - примитивный многочлен над полем Fa. то каждая рекуррентная
последовательность с ненулевым начальным вектором, задаваемая указанным
лниейным рекуррентным соотношением" является последовательностью
максимального периода над полем Fa* Нели в качестве вектора начального
состояния выбрать произвольный ненулевой вектор, то мы получим
последовательность So, sb ..." имеющую в соответствии с теоремой 8.33
минимальный период 27 - 1 = 127. Таким образом, все возможные ненулевые
векторы нз Fs встречаются в качестве векторов состояний этой
последовательности. Любая другая последовательность максимального
периода, получаемая из этого же линейного рекуррентного соотношения,
представляет собой некоторый сдвиг последовательности s0, slf ... . ?
*
§ 3. Производящие функции
До сих пор при изучении линейных рекуррентных последовательностей мы
пользовались понятиями линейной алгебры, алгебры многочленов и теории
конечных полей. Использование алгебраического аппарата формальных
степенных рядов позволит нам получить Другие замечательные результаты,
связанные с линейными рекуррентными последовательностями.
Пусть дана произвольная последовательность s0, s1( ... элементов поля
Fff* С этой последовательностью можно связать ее производящую функцию от
переменной х, которая является просто формальным выражением вида
ОО
G (х) = Sq -j- S^X -j- SjX^ -j- * ' * "j- sftxn -j- * * * = SnXn, ($* 13)
n-0
где x - формальная переменная. В основе этого подхода лежит мысль, что в
функции G (х) "собраны" в определенном порядке все члены
последовательности s0, sit ..." так что функция G (jt) может некоторым
образом отражать свойства этой последовательности. Название "производящая
функция", строго говоря, является неправильным, так как мы рассматриваем
