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

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

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

пока мы не получим все k неприводимых сомножителей мно члена / (х).
Описанный процесс должен в конечном счете привести к хождению всех
неприводимых делителей многочлена f (х). ствительно, если рассмотреть два
различных нормирован неприводимых делителя многочлена / (х), например /х
(х) и то рассуждение, следующее за сравнением (4.3), показывает для
каждого /, 1 <; / < k, существуют элементы сп и поля такие, что
выполняются сравнения hj(x) = сд ( h Mb М f (mod /2 (х)). Допустим, что
сп = сдля f к. Тогда, учитывая, что любое решение h (х) сравн
(4.3) является линейной комбинацией базисных многочл hx (х), hk (х) с
коэффициентами из [F^, получаем, что для бого такого решения h (х)
существует элемент с ? [Fg, та что h (х) = с (mod Д (х)), к (х) = с (mod
/2 (х)). Но рассуждав которое привело к сравнению (4.3), показывает, что
существ^ в частности, и такое решение h (х) сравнения (4.3), что h{
= 0 (mod fi (х)) и h (х) = 1 (mod /2 (х)). Полученное проти чие
доказывает, что сп ф cj2 для некоторого /, 1 ^ k { нее, для некоторого /,
2 / < k, поскольку hi (х) - 1), Поэт
многочлен hj (х) -сл будет делиться на ft (х), но не на /, Отсюда
следует, что любые два различных нормированных приводимых делителя
многочлена / (х) обязательно "отдели) друг от друга (в указанном смысле)
некоторым базисным мн членом hj (х).
Этот алгоритм разложения многочлена /, основанный па хождении /-
разлагающих многочленов (путем решения сист
(4.6) линейных уравнений) носит название алгоритма кэмпа.
4.2. Пример. Разложим многочлен / (х) - Xs + х8 4* i + х3 1 над полем
[р2, применяя алгоритм Берлекэмпа. как НОД (/ (х), /' (х)) = 1, то
многочлен / (х) не имеет
ебуется найти вычеты одночленов 2 и I = 0, 1, 7. Это приводит
к
v Ш
.-Г
, ш
сомножителей. Нам т по модулю / (х) для q -дующим сравнениям по модулю
/(х):
х° = 1,
РЖ
§ L Разложение многочленов над малыми конечными полями
193
В
а матрица В
В
,а В имеет внд
1 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
1 0 0 1 1 0 1 0
1 0 1 1 1 1 0 0
0 0 1 0 1 1 1 1
1 1 0 1 1 1 0 0 ,
еет вид
( 0 0 0 0 0 0 0 01
0 1 1 0 0 0 0 0
0 0 1 0 1 0 0 0
0 0 0 1 0 0 I 0
1 0 0 1 0 0 1 0
1 0 1 1 I 0 0 0
0 0 1 0 1 1 0 I
1 1 0 1 1 1 0 I.
Несложные вычисления показывают, что матрица В-/ имеет ранг б и векторы
(I, 0, 0, 0, 0, 0, 0, 0) и (0, 1, I, О, О, I, 1, I) образуют базис
пространства решений однородной системы (4.6), соответствующей матрице В-
/. Этим векторам соответствуют
X + X2 + х + # + Я7-
многочлены hx (х) = 1 и h% (х) числя я при помощи алгоритма Евклида НОД
(/ (х), /г2 (ж)
ДЛ я
Вы-
с)
элементов с ? Г2, получаем, что НОД {/ (х), /г2 (х)) = х6 + 4 х5 {- х4 +
х 4- 1, НОД (/ (х), /гг (х)-1) = х2 4" х + 1. В итоге получаем следующее
каноническое разложение многочлена / (х):
/ (х) = (х6 + х5 + х4 4~ х + 1) (х2 4" х -h I). ?
Другой метод получения /-разлагающих многочленов связан о построением
некоторого семейства многочленов, в котором имеется по крайней мере один
/-разлагающий многочлен. Пусть снова / обозначает произвольный
нормированный многочлен степени п > 1, не имеющий кратных сомножителей, н
пусть/ = ft ... fk - его каноническое разложение в кольце [х], причем deg
(fj) - - Hj для 1 < j ^ k. Еслн N - наименьшее натуральное число, такое,
что x^N ¦= х (mod / (х)), то из теоремы 3,20 получаем, что НОК (яА, nk),
при этом также нетрудно видеть, что N - степень поля разложения F
многочлена / над Wq. Рассмотрим
многочлен Т ? (F9 [х] вида Т (х) - х -Ь xq 4" 4" ¦¦¦ 4" xqN~1.
П Зак, 222
194
Гл. 4. Разложение многочленов на множители
Положим 7i (х) 7 (xf) для i f IN. Следующий результат
называет, что в рассматриваемом случае (когда многочлен f г приводим в
кольце fq [х\ и не имеет кратных сомножителе среди многочленов Tt (х), 1
< i пу найдется хотя бы /-разлагающий многочлен.
s -3
4,3. Теорема. Пусть многочлен без кратных сомножитеЖ
/ ? IFq fx] приводим в Fg. [х]. Тогда {во введенных выше обознт
ниях) по крайней мере один из многочленов Tif 1 < / <' л -является f-
разлагающим многочленом.
Доказательство. Учитывая сравнения х?Л н х (mod / (х)), видим, что каждый
из многочленов Tf удовлетворяет уело]
7i (mod/). Допустим теперь, что для всех многочленов 1 -< i п - С
разложение многочлена /, даваемое форму (4.2), тривиально (при h ~ Tt).
Это означает, что существуют sj
cn-i С S> такие, что Tt (х) ^ ct (mod / (х)) jf 1. Рассматривая = N
как элемент поля
Г?
менты С|,
I =
* * * q
1, п '
получаем сравнения Т (х{) ~ Сг (mod / (х)), i - О, I, ..., п Для любого
многочлена
п-i
8 {*)=¦- ? atx' (z Fq[x]
i-О
!•
степени меньше гс мы имеем тогда
л-S л-1
? а,Т (*¦') н ? я.-е, (mod f (•*))•
Т (В Ш = Г
Fi -1
L ai% \ (-0
'7;й
:ГГ
0
f=0
Полагая
' vs ЙУ ?
гс-1
& {ft) Fа у
получим
¦'ад
7 (g (х)) = с {?) (mod /;- (х)), / - 1, /г
m
Так как N = НОК (пъ %), то по крайней мере одно из лых чисел M/nj, скажем
Ninlt не делится *) на характерист поля fq. Пусть 0| - корень многочлена
Предыдущая << 1 .. 78 79 80 81 82 83 < 84 > 85 86 87 88 89 90 .. 371 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed