Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
разложение многочлена /.
Но существует модификация изложенного метода, когда вместо многочленов 74
строятся связанные с ними многочлены Rit которые способны отделить все
неприводимые сомножители многочлена / сразу. Предположим (без
ограничения общности), что
/ (0) Ф 0. Пусть ord (/ (х)) = е, так что / (х) делит двучлен
хе - 1.
Поскольку многочлен / (х) не имеет кратных сомножителей, то на основании
следствия 3.4 и теоремы 3.9 числа ей q взаимно просты. Пусть i - целое
неотрицательное число; обозначим через mt наименьшее натуральное число,
удовлетворяющее сравнению
щ ¦ ,
Xiq 1 ^ xi (mot| / ДО), (4Л0)
Пусть теперь
Rt (х) = X1 4" Х*4 + + * * • + Х*9(tm)1
- многочлен над Fg. Поскольку сравнение (4.10) эквивалентно
сравнению
iqm* = i (mod e)f (4.11)
которое в свою очередь эквивалентно сравнению q(tm)1 =
- 3 (mod (е/НОД (е, i))), то отсюда следует, что число mt является
Указателем, которому принадлежит число q по модулю е/НОД (е,
19В
Гл. 4. Разложение многочленов на множители
е). Сравнивая определения многочленов 74 и Rit легко уста& ливаем а), что
TAX) - -jL Rt U) (mod/(*)).
Ясно, что для всех i справедливо сравнение Rg ~ Ri (mod так что
многочлены Rt можно использовать вместо h в форм) (4.2). Покажем теперь,
что многочлены Rt обладают указав выше свойством.
'Л
'^4
¦
4.5. Теорема. Пусть приводимый над полем Fq нормаров{ многочлен / не
имеет кратных сомножителей, и пусть f (0) ?= _ и ord (/) = е. Тогда,
используя вместо h (х) в формуле (4.2)
_ ^ %-|
члены Ri (х) - х1' + х^ + хщ ф ... ф х^ 1 , 1 < i < е
где числа пц определяются условием (4.10), можно отделить,
неприводимые сомножители многочлена /.
е-1
Ъ-У.у,
\
А
Доказательство. Пусть h (х) = 'Цаф ? Fg lx]
;>х
Ы:.
ММ
ре шей
сравнения А (х)? = h (х) (mod (хе - 1)). Если рассматривать дексы
коэффициентов ах как вычеты по mod е, то ввиду взанмй
I
сравнение h (х) = ?
{=0
(mod (хй - 1)), так как при i - 0, 1, в - 1 числа iq пр гают полную
систему вычетов по mod е. А поскольку h (х)?
:г* %
простоты чисел q н е получаем
е-\
2 аре1*. то 1=?0
&-1 е
? сс
j --О
? a*gx^(mod(xe
i=0
!))•
•:;й
щ
.¦¦т
о
л.:
Рассматривая здесь показатели как вычеты по модулю е, мы дим, что
соответствующие коэффициенты равны. Значит, at
- aiq для всех так что для всех i выполняются равенства ец
- aiq = Qiq% - . Поскольку т* - наименьшее натуральное ч
ело, для которого имеет место сравнение (4.11), то
А(х) = ? aj/?j(x)(mod(xg - 1)),
i 6 J
где множество J содержит по одному представителю от каждо класса
эквивалентности при следующем определении отиошеий| эквивалентности для
г\, 12 6 2 считаем, что ix ~ i2 тогда
щ
¦г, :<5
.
т
4 Так как Rt (je)^ - ^
i-0
- Rt (х) (mod f {x)}. - Прим. перев.
x
m.-I
?
/5=9
m
X
iq _
/ =
m •-I
it
?
/=i
X
L.lii
¦¦4.
§ 1. Разложение многочленов над малыми конечными полями 199
только тогда, когда имеет место сравнение ix ~ (mod е) для некоторого t
5s 0. Таким* образом, для подходящих элементов1)
bi ? IFg
г-I
h (х) ~ 2 &iRi М (mod (х* - 1)). (4.12)
/=о
Пусть теперь Д (х) и Д (х) - два различных нормированных неприводимых
делителя многочлена / (х) (а следовательно, и двучлена хе - 1). Согласно
рассуждению, которое привело к сравнению (4.3), существует такое решение
h (х) ? fg НИ сравнения h {xf xi h (х) (mod (ха - 1)), что deg (h (х)) <
е и при этом
h (х) ~ 0 (mod Д (х)), h (х) ~ 1 (mod Д (х)). (4.13)
Поскольку Rgi ~ Ri (mod /), то из раесуждеиця, следующего за сравнением
(4.3), вытекает существование таких элементов сп, Иг е Fq, что Rt (х) =
сп (mod Д (х)) и Rt (х) ~ ct2 (mod Д (х)) для всех /, 0 < I с е - 1. Если
для всех этих i имеет место равенство сц ~ ci2> то из (4.12) следует, что
для некоторого с ? Fq имеют место сравнения h (х) ~ с (mod Д (х)), h (х)
= с (mod /2 (х)), но это противоречит сравнениям (4.13). Поэтому должно
быть Пт Ф ?i2 Для некоторого /, 0 < / < е - 1 (точнее, для некоторого i,
1 < i < е - 1, так как R$ (х) = 1). В таком случае многочлен Ri (*) - Сц
будет делиться на Д (х), но не на /2 (х). Следовательно, используя этот
многочлен Rt (х) вместо h (х) в формуле (4.2), мы отделим fl (х) от /2
(X). ?
Из доказательства теоремы 4.5 видно, что все неприводимые делители
многочлена f могут быть отделены многочленами Rtt где i пробегает
ненулевые элементы множества J. Однако для нахождения множества J
требуется знать порядок в многочлена Д прямой же подсчет числа в (т. е.
без использования канонического разложения многочлена/),.как правило,
чересчур громоздок.
Такая проблема не возникает в следующих двух частных случаях - двучлена /
(х) - хе - 1 н е-кругового многочлена f (х) - ~ Qe (х), поскольку в обоих
этих случаях, очевидно, ord (хе - 1) = - ord (Qe (х)) = е. Оказывается,
что многочлены Rt очень удобны л ля разложения таких двучленов и круговых
многочленов.
4.6. Пример. Найдем каноническое разложение кругового многочлена QB2 (х)
в кольце F3 1х]. Согласно теореме 3.27,
О ~ (^-0(^-1) _
