Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
применяем лемму 3.6 и получаем, что каждое из чисел ef,
1 i k, делит е, а потому и с делит е. Это означает, что с = е.
В действительности, используя то же доказательство, можно показать, что
порядок наименьшего общего кратного нескольких ненулевых многочленов
равен наименьшему общему кратному порядков этих многочленов.
ЗЛО. Пример. Найдем порядок многочлена / (х) = х10 + х9 + х3 -J- х2 + 1 С
Fa U1- Каноническое разложение его над полем fa имеет вид
f (х) = (х2 + х + I)3 (х4 + х + 1).
Так как ord (х2 + х + I) = 3, то из теоремы 3.8 получаем, что ord ((** -f
х + I)3) = 12. Далее, ord (х4 4* х -Ь 1) = 15, так что из теоремы 3.9
получаем, что ord {/) = НОК (12, 15) ~ 60. Заметим, что ord {/) не делит
число 210 - 1 - 1023; это показывает, что для приводимых многочленов
следствие 3.4 не обязательно выполняется. ?
На основании доказанного можно дать следующую общую формулу для порядка
многочлена. При этом предполагается, что все рассматриваемые многочлены
имеют положительную степень я ненулевой постоянный член.
3.11. Теорема. Пусть Fe - конечное поле характеристики р.
Если f - afx1 ... fkh - каноническое разложение е кольце [х] многочлена /
(х) С Tq 1х] положительной степени, такого, что f (0) ф о (m. е. а ? пъ
пк С IN и Д, ..., fh - различные нормированные неприводимые многочлены из
IF" 1х], отличные
0гп х), то
ord (/) = ord (af"1 ... flh) = ^HOK (ord (/i), ord (/*))>
(r) Зак. 222
114
Гл. 3. Многочлены иад конечными полями
HSU^^frjgir уга^Ь^уй щ цр |1-v-- " ¦ рTiTrfT*"" ~~ -^,цлцг........туа-п
tfiynnff тгп t • 1 • 'мТтТй^ >*И^й:т______^
~ j^TiTi>- "T^W
¦ I -¦¦- ¦ | ||р-'-'^~ььЬЛ-^г№^-'-^'-|г'Кт>Г|Л) , . ) ,4 i-^n-
,. -yt
•W№tAU№№^-Ak
где¦ i - наименьшее целое число, удовлетворяюще неравенству pi ^ шах \пъ
пк\.
Один из методов определения порядка неприводимого многочлена / из F(/
[х], удовлетворяющего условию { (0) Ф 0, основан ;
на том факте, что порядок е многочлена / является наименьшим натуральным
числом, удовлетворяющим сравнению
ж* ет I (mod / (*)).
Кроме того, согласно следствию 3.4, число е делит qm - it где т - степень
многочлена /. Предполагая, что qm > 2, будем исходить из разложения числа
qm -- 1 на простые сомножители:
&
ЛК
'•Й:
т
п
/=1
Pi
J
Для каждого /, 1 "С /<4$
J
^ ^ *, найдем вычеты одночленов х по модулю / (х) (т. е. остатки при их
делении на f (х)). Обычно это делается перемножением подходящим образом
выбранного набора
вычетов по модулю f (х) степеней х, хд хЛг, х?т 1 переменной х.
При этом, если окажется, что ф\ (mod / (х)), то число е
делится на рр, а если x^~l^!Pi лится на р/, В последнем случае мы
выясняем, будет ли число в
t j~~"j f
делиться на р/ , р/ , р/, вычисляя соответственно вычеты
по модулю / (х) следующих степеней переменной х:
$
е 1 (mod / (х)), то число е не де-
х
* * *
*
.г
У
;Ь
Такой подсчет проводится для каждого простого делителя pj числа (f1 - 1,
ив итоге находится число е = ord (/).
Ключевым моментом указанного метода является разложений на простые
сомножители натурального числа qm - 1. Составлены обширные таблицы для
полного разложения чисел такого вида* особенно для случая q - 2.
Существует связь между порядками некоторых многочленов, которые можно
получать друг из друга простыми алгебраическими преобразованиями.
Типичным примером может служить следующее преобразование.
3.12. Определение, Пусть дан многочлен
1
/ (х) = апхп + аПтХх
п-1 _.jL * * в Д.
ух 4- <*0 € ipq W
с пп 0. Тогда возвратный (или двойственный) к нему многочлен /*
определяется так:
/* (х) = хпf (
UW.i.nir fll
П0х
п
* *
" Г' ~Т"~ ^
а
*
•&
§ !. Порядки многочленов и примитивные многочлены
125
3.13. Теорема, Пусть f - ненулевой многочлен из Fg [ж] и /* -возвратный к
нему многочлен. Тогда ord (/*) = ord (/).
Доказательство. Сначала рассмотрим случай / (0) ^ 0. Тогда утверждение
вытекает из того факта, что многочлен / (ж) делит хе - 1 в том и только
том случае, если многочлен /* (ж) делит хе - 1. Если же / (0) - 0, то
запишем / (ж) = xhg (ж), где h ? ? N , g ? Fg [ж] и g (0) Ф 0. Тогда из
ранее доказанного и из определения порядка следует, что ord (/) = ord (g)
= ord (g*) = =- ord (f*), где последнее равенство вытекает из равенства
g* -
= /*. ?
Имеется также тесная взаимосвязь между порядками многочленов /(ж) и f (-
х). Поскольку для поля характеристики 2 имеем f (-ж) = f (ж), то
достаточно рассмотреть лншь поля нечетной характеристики.
3.14. Теорема. Для нечетного q пусть / С (Fg[ж] - многочлен положительной
степени, такой, что f (0) ф 0, и пусть е и Е - соответственно порядки
многочленов f (ж) и / (-ж), Тогда Е - е, сел гг е делится на 4, и Е = 2с,
сел гг е нечетно. Еслгг же с 2/г, где /г нечетно, то Е = е/2 в случае,
когда все неприводимые делатели многочлена / имеют четный порядок, и Е ~
е в противном случае.
Доказательство. Так как ord (/) - е, то многочлен / (ж) делит х2е - 1, а
значит, многочлен / (-ж) делнт (-ж)2е - 1 = х2е - 1. Поэтому число Е
делит 2е (согласно лемме 3.6). Аналогично показывается, что число е делит
