Научная литература
booksshare.net -> Добавить материал -> Физика -> Лидл Р. -> "Конечные поля. Том 1" -> 82

Конечные поля. Том 1 - Лидл Р.

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1 — М.: Мир, 1988. — 430 c.
ISBN 5-03-000065-8
Скачать (прямая ссылка): konechniepolya1988.djvu
Предыдущая << 1 .. 76 77 78 79 80 81 < 82 > 83 84 85 86 87 88 .. 371 >> Следующая

"малым" илн "большим" является данное конечное поле. В § I мы опишем те
алгоритмы, которые более удобны для "малых" полей, а в § 2 - те, которые
лучше работают для "больших" конечных полей. Некоторые из этих алгоритмов
сводят проблему разложения многочленов к задаче отыскания корней
некоторых других многочленов. Поэтому в § 3 вопрос об отыскании корней
многочленов рассматривается с вычислительной точки зрения.
§ 1. Разложение многочленов над малыми
конечными полями
Для любого многочлена / ? Fq lx] положительной степени существует
каноническое разложение в кольце [Р5 U1 (теорема 1.59). При построении
алгоритма такого разложения, оче-видно, достаточно ограничиться
рассмотрением лишь нормирован-
188
Гл. 4. Разложение многой ленов на множители
s ft
ных многочленов. Таким образом, нашей целью является пр< ставление
нормированного многочлена f ? [Fq [х] положите* ной степени в виде
произведения
•'V3S
f
Л/ /у. : ^'с
(4
где ..., fk - различные нормированные неприводимые дел тели многочлена f
в кольце U'], а еъ ek - натураль числа.
Прежде всего мы упростим свою задачу, показав, что указ^ ную проблему
можно свести к проблеме разложения многочле без кратных неприводимых
сомножителей, т. е. такого мно члена f, для которого в каноническом
разложении (4.1) все цоК затели elt равны единице (это равносильно
отсутствию у мн гочлена f кратных корней). Для этого мы сначала найдем,
при няя алгоритм Евклида, многочлен
I
Ш
УМ
d (X) - НОД (f (х), Г (*))
- наибольший общий делитель многочлена f и его производной
Если d (х) - I, то в силу теоремы 1.68 многочлен f (х) не и кратных
сомножителей*). Рассмотрим случай, когда d (х)
= f (х). Тогда, очевидно, должно быть f (я) - 0, а это что / (х) - g (х)р
для некоторого многочлена g (х) ? Fg где р - характеристика поля
Указанную процедуру реду ции можно, если это необходимо, повторить
применительно к МЙ
гочлену^ (х) и т. д., пока не получим представление f (х) -- h (л где А'
(/) Ф 0.
Если же многочлен d (х) отличен от I и от f (х), то он являё^
нетривиальным делителем многочлена f (л), и в этом случае мир ' член f
(x)id (х) не имеет кратных неприводимых сомиожител# Мы придем к
разложению / (х), разложив по отдельности мно: члены меньшей степени d
(х) н f (x)Id(x). В случае если многоч d (х) все еще имеет кратные
множители, мы для него повтори указанный процесс редукции. '
Применив этот процесс нужное число раз, мы сведем исходи^ проблему к
задаче разложения некоторого числа многочленб не имеющих кратных
неприводимых сомножителей. Каноиичее разложения этих многочленов сразу же
приведут к каноническ разложению исходного многочлена. Эти соображения
поз воля нам сосредоточить свое внимание на многочленах, не имеют кратных
неприводимых сомножителей. Следующая теорема ш ляется основной.
.rav>
..•Л:
&<>
ш
*) Речь идет о каноническом разложении. - Прим* перев.
- *-
§ 1. Разложение многочленов над малыми конечными полями 189
4,1. Теорема. Если / ? Fg [х]-нормированный многочлен положительной
степени и многочлен h ? Fg fx] удовлетворяет условию к* = h (mod /), то
f(x)= П НОД (/ (х), h (х) - с). (4.2)
0 € F g
Доказательство. Каждый наибольший общий делитель из правой части
равенства (4.2) делит многочлен / (ж). Поскольку многочлены h (х) - с, с
? Fg, попарно взаимно просты, то взаимно простыми являются и их
наибольшие общие делители с / (х), т. е. сомножители правой части (4.2),
и, следовательно, правая часть равенства (4.2) делнт многочлен / (х). С
другой стороны, многочлен /(х) делит разность
h (х)ч - h (х) = П (h (х) - с), ,
с € ЕР g
и, значит, / (х) делнт правую часть равенства (4.2). Итак, обе части
(4.2) являются нормированными многочленами, каждый из которых делит
другой, и, значит, они должны совпадать. ?
Вообще говоря, формула (4.2) ие дает полного разложения многочлена /,
поскольку многочлен НОД (/ (х), h (х) - с) может оказаться приводимым в
кольце Fg lx J. Если же h (х) = = с (mod / (х)) для некоторого с ? Fg,
теорема 4.1 вообще приводит к тривиальному разложению /(ле) и потому
бесполезна. Если многочлен h (ле) таков, что теорема 4.1 приводит к
нетривиальному разложению многочлена / (ле), он называется f-разлагающи м
многочленом. Любой многочлен h ? Fg [ле], обладающий свойствами h9 = h
(mod/) н О < deg (к) < deg (/), очевидно, является /-разлагающим. Чтобы
на основе теоремы 4.1 получить алгоритмы разложения, мы должны найти
способы построения /-разлагающих многочленов. Но уже на этом этапе ясно,
что, поскольку разложение, основанное иа формуле (4.2), связано с
вычислением g наибольших общих делителей, то прямое применение этой
формулы возможно лишь для малых конечных по-лей Fq (т. е. для небольших
значений д).
Первый способ построения /-разлагающих многочленов использует китайскую
теорему об остатках для многочленов (см. упр. 1.37). Допустим, что
многочлен / не имеет кратных сомножителей, так что / = Д ... fh -
произведение различных нормированных несводимых многочленов над полем Fg-
Предыдущая << 1 .. 76 77 78 79 80 81 < 82 > 83 84 85 86 87 88 .. 371 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed