Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
V52W- (хгв - I) - i) "
= Xй1 - X22 -f- X20 X18 4- - X14 -f- X12 -
- х10 4- х8 - xe + х4 - х2 4- Е
t i •*
*) Здесь Ь. = й . еслн i ? У, и Ь. = 0, если i ^ J. - Прим. перев,
200
Гл. 4, Разложение многочленов на множители
'.¦т
ж
Рассмотрим теперь многочлен Rx (х) - х + х3 4- х8 + х27 -f хш. Ввиду того
*), что х2& =?. -1 (mod Q52 (х)), получаем, R1 (х) (tm) 0 (mod Q52 (х)), так
что Rx не является (^"разлагающ многочленом. Переходим к следующему
многочлену (х) = х + Xе + хи. Для него получаем
НОД (Q52 (.х), R2 (X)) xs - х
Л
НОД (Q5., (х), R2 (х) НОД (Q62 (X), R2 (х)
1) = хя + х1 -1) = хш + хы
" S (*).
1,
х2 + 1,
•:5"
что
Ж
?
х8 + х* + X2 + Щ
-"У-
так что из формулы (4.2) следует равенство
:т
Q52 (х) = (X* - X2 + 1) (*в + Я1 - Xs -1" 1) g (х).
Л. '
¦Ы
Согласно теореме 2.47 (ii), круговой многочлен Q52 (х) в кол Fs fx]
разлагается в произведение четырех неприводимых сом" жителей степени 6.
Так что остается только разложить мнош член g (х). Поскольку R3 (х)
" Ч г т " Ч г
+ хш ~ 0 (mod Q52 (х)), переходим к следующему многочл#;
т
- X3 + X9 + Х2Т + X81 +
R 4 (х)
- X2
х4 + х12 + ^ • Заметив, что х12
1 (mod g (х)) и хзв = /?4 (х) = х10 + х8 -
X10 + х8 - Xе
х10 (mod g (х)), получим, что
X
&
X
2
1 (mod g (х)).
Поэтому
НОД (3 (х), Ri (X)) = НОД (g (X), х1а + Xй - х" - хг - \)
НОД (g(x). Ri (х) + 1) = НОД (g (х), х10
'8
Я
6
X2)
- X
6
X* + х2 + 1,
НОД (g (х), Rt(x)-l) = НОД (g (х), х
л;
в
X4 + 1*
X8 - Xе - X2 "Ь 1)4
"11
•• г/
ч
Таким образом, искомое каноническое разложение многочла Q52 (я) имеет вид
Q52 (¦*) (tm)
= (х° - х2 -|-!) (х6 + х4 - х2 + i)(xe-x4 + х2+ i)(x8-x4 + 1)*
'Ж
• "".s •, * ^
§ 2. Разложение многочленов над большими
конечными полями
Если - большое конечное поле, т. е. число д велико, практическое
применение методов предыдущего параграфа новится затруднительным. Хоть мы
и можем, затратив определи
-т
"й
KY
*) Так как хи + 1 - (л;&- - l)/(.r26- 1) содержит все первообразные ко]
52-й степени из 1. -- Прим.. перев.
§ 2. Разложение многочленов над большими конечными полями 201
ные усилия, найти f-разлагающий многочлен, однако прямое использование
основной формулы (4.2) становится уже нереальным, так как оно требует
подсчета q наибольших общих делителей. Поэтому для того, чтобы сделать
возможным использование /-разлагающих многочленов и для больших конечных
полей, необходимо изыскать пути сокращения числа элементов с ? Fgf для
которых в формуле (4.2) нужно подсчитывать наибольшие общие делители.
Заметим, что в контексте, связанном с разложением многочленов, мы будем
считать порядок q конечного поля Fg "большим", еслн он существенно больше
степени разлагаемого
многочлена.
Пусть снова f- произвольный нормированный многочлен степени п из кольца
Fg [х], разлагающийся в произведение k различных нормированных
неприводимых сомножителей над полем Fg. Допустим, что многочлен h ? Fg
[х] удовлетворяет условиям № = h (mod /) и 0 < deg (h) < н, так что он
является /-разлагающим многочленом. Поскольку различные наибольшие общие
делители из правой части формулы (4.2) взаимно просты, то ясно, что не
более k из них могут быть отлнчиы от 1. Задача состоит в том, как a
priori охарактеризовать те элементы с ? Fgf для которых НОД (/ (х), h(x)
- с) Ф 1.
Одну из таких характеризаций можно получить, применяя теорию результантов
(см. определение 1.93 и последующие замечания). Пусть R (/ (х), h (х) -
с) - результант многочленов f (х) и h (х) --с, где в качестве формальных
степеней берутся степени этих многочленов. Тогда НОД (f (х), h (х) - с) Ф
1 в том и только том случае, если R{j{x)t h(x) - c) = 0. Так мы приходим
к рассмотрению функции
F{y) = R (f (х)* h (х) - у),
которая, очевидно, является многочленом степени, не большей п,
относительно переменной у (учитывая представление результанта в виде
определителя). Ясно, что НОД (/ (х), h (х) - с) Ф 1 в том и только том
случае, если элемент с является корнем многочлена F (у) из поля Fg.
Многочлен F (у) можно найти непосредственно из его определения; для этого
потребуется вычислить определитель порядка не более чем 2п - 1,
элементами которого являются либо элементы из поля Fg, либо лииейиые
многочлены от у с коэффициентами из Fq. Однако во многих случаях
предпочтительнее другой способ, состоящий в следующем. Выберем п + 1
различных элементов с(ь с,, ...,сп нз Fg и подсчитаем результанты rt - R
(f (х), h (х) -
сД, i - 0, 1, п. Тогда тот единственный многочлен F (у) степени ие
превосходящей и, для которого F (Д - rit i ~ 0, и, можно получить с
помощью интерполяционной формулы
202
Гл. 4. Разложение многочленов на множители
Лагранжа (см. теорему 1.71). Этот метод имеет еще то преимуад етво, что
если какие-либо элементы rt равны нулю, то мы автом тически получаем
корни многочлена F (у) из поля Fg. Во всяк случае вопрос о выделении тех
элементов с ? для которщ НОД (/ (х), h (х) - с) Ф 1, теперь сводится к
вопросу нахожд< ния корней некоторого многочлена в поле Fg. Вычислительна
