Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
0 0 0 0 0
0_1 8 -3 -10
10 10 0 1 -9
7 9 -8 10 -11
0 -4 7 7 2
0 -10 9 2 -9
Начнем алгоритм с г0 (х) = х и /у, (х) = / (х). Из (4.20) и (4,21)
получаем многочлен sx (х) ^ -10х5 - Зх4 Т 8х3 - х2 -f 5, и, приводя его
по модулю К0 (х), находим rx (х) - sx (х). Согласно теореме 4.13, имеем
gx (х) = dx (х) =- НОД (/> (x)t rx (х) - х) = х -
- 4. Кроме того, Fx (х) = Р.0 (x)/di (х) = х5 + х4 4- 9х3 + 4х2 + -Г' 1
lx -f- 4,
На втором шаге мы вновь применяем (4.20) и (4.21) для нахождения
многочлена $2 (х) ~ бх5 - 8х4 1- Эх3 - Юх2 - 11, и приведением его по
модулю Рг (х) получаем г2 (х) =- Юх4 + Юх3^ -
- 7х2 - 9х - 8. Согласно теореме 4.13, g2 (х) = d2 (х) --
- НОД (Fi (х), г2 (х) - х) = х2 - х + 7. Кроме того, F2 (х) - ¦ = Fx
(x)!d% (х) ~ х3 f- 2х2 -f 4х - б. Но, согласно первой части (4,18), все
неприводимые делители многочлена F% (х) имеют степени не менее 3, поэтому
многочлен F% (х) сам должен быть неприводимым в кольце F3§ [х), так что
g;i (х) = Р2 (х). Таким образом, мы получаем частичное разложение
/ (х) = (х - 4) (х2 - х -|- 7) (х3 j 2х2 + 4х - 6);
которое в данном случае уже оказывается каноническим разложением
многочлена / (х) в кольце Fa.* UL ?
В
1
5
10
0
11
-3
§ 3. Вычисление корней многочленов
213
§ 3. Вычисление корней многочленов
В предыдущих параграфах мы видели, что проблему канонического разложения
некоторого многочлена над конечным полем часто можно свести к задаче
нахождения корней в этом поле некоторого вспомогательного многочлена. Но
вычисление корней многочлена, безусловно, представляет и самостоятельный
интерес.
Вообще говоря, мы ставнм следующую задачу. Пусть задан многочлен / ? lFr
[х]; требуется найти его корни в некотором расширении fq поля рг. Однако
достаточно рассмотреть ситуацию, когда нужно найти корни многочлена / ?
Fg [х] положительной степени, лежащие в самом рд, так как многочлен над
подполем всегда можно рассматривать как многочлен над всем полем.
Ясно, что каждый алгоритм разложения многочлена / в кольце pg fx], в
частности, является и алгоритмом нахождения его корней в поле Fg. так как
эти корни определяются линейными сомножителями канонического разложения /
в кольце Fg fxL Поэтому алгоритмы, рассмотренные в предыдущих параграфах
этой главы, можно использовать также и для нахождения корней. Однако эти
алгоритмы чаще всего являются не самым эффективным способом вычисления
корней многочлена, когда ставится именно такая задача. Поэтому мы
рассмотрим методы, более приспособленные для этой цели.
В качестве исходного шага полезно выделить ту часть многочлена f, которая
содержит все его корни в поле Fg- Это достигается вычислением НОД (/ (х),
х* - х). Ввиду того что двучлен х<? - х является произведением всех
нормированных линейных многочленов кольца fg [х], указанный наибольший
общий делитель равен произведению всех тех нормированных линейных
многочленов иад Fg, которые делят f', поэтому его корнями являются те и
только те корни многочлена f, которые принадлежат полю Fg. Учитывая это,
можно без ограничения общности предполагать, что все корни многочлена,
для которого мы намерены найти корни в поле Fg, принадлежат полю Fg а
притом различны, т. е. что / является произведением различных линейных
нормированных многочленов из [х].
Один полезный метод нахождения корней многочленов мы уже рассмотрели в §
4 гл. 3; о и был основан на определении аффинного кратного для данного
многочлена. Этот метод мы проиллюстрировали примером 3.55.
Переходя к другим методам, рассмотрим сначала случай простого поля Рр.
Как уже было отмечено, достаточно рассмотреть лишь многочлены вида
214
Гл. 4. Разложение многочленов на множители
различные элементы поля р.. Если чи(
где сх,
&п 1**иг"Г1#ж у р.
мало, то найти корни многочлена / можно просто методом п ошибок, т. е.
простым вычислением всех значений /(0), f (Щ
.."tip - п.
Если же число р велико, то можно применить следующий ем. Пусть Ь ? fp,
где р нечетно. Рассмотрим равенство
/ (X - Ь)
Ф + С;))-
Заметим, что многочлен
= X + 1) (Я<Р-1>/2
телем многочлена f (х ~
П
П (х
t=1
f (х - b) делит двучлен хр
$
¦:>-Л
>.Х'
¦< *
- 1). Если при этом х является 6), то f (-Ь) - 0, и нами найден
JM
из корней многочлена /. Если же х не является делителем f (х
ТО '
f (х - Ь) = НОД if (х - Ь), jttp-o/2 + 1) НОД (/ (х - ft)
Л(р-1>/2_ 1).
s>*
Равенство (4.22) мы теперь используем следующим образом, ведем степень
х(р~1^2 по модулю / (х - Ь) (например, прим технику последовательного
возведения в квадрат, рассмотрев вслед за теоремой 4.13). Если ф ±1
(mod f (х - &))
равенство (4.22) даст нетривиальное частичное разложение мн члена f (х -
Ь). Заменяя х на х + Ь, мы получим нетривищ частичное разложение
многочлена f (х). В довольно редком чае, когда х*?-*>/2 = ±1 (mod f (х -
b)), можно исполь другое значение Ь. Таким образом, изменяя по мере
необходн выбор элемента Ь, мы можем найти либо некоторый корень м$ члена
f, либо его нетривиальное частичное разложение, Пр^
