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

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

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1 — М.: Мир, 1988. — 430 c.
ISBN 5-03-000065-8
Скачать (прямая ссылка): konechniepolya1988.djvu
Предыдущая << 1 .. 88 89 90 91 92 93 < 94 > 95 96 97 98 99 100 .. 371 >> Следующая

Пример 4.16. Рассмотрим поле fe4 - F2 (Р), где р - некоторый корень
неприводимого многочлена х8 4- х -f 1 из 1*3. и
пусть
/ (X) = X4 + (р* + р4 + р3 + р2) X3 + (Р" + р4 + р2 + р +
+ 1) х2 -Т (р4 *Т Р3 *Т Р) х -Т (р3 *Т Р) (; F84 ^3.
Используя сравнение
х8 = (р* + Р + 1) X3 + (Р4 + Р3 + р2) *2 + (Р5 + р3 + Р2 +
+ 1) X 4- (р5 + р4 + Р2 + 1) (mod / (х)),
получим последовательным возведением в квадрат следующие сравнения по
модулю f (х):
№ t
** = (р"4-р1+р3+р!)*ч_ (р"+р.+ра+р+1)^+(р4+р3+р)д[+(р"+р)>
Xs = (Э"+Р=Ч-Р")ДС'Ч- (р"+р+|)*Ч(Р5+Р+1>*+<Р5+Р4).
(рЧР3+Р)*3+ (Р3+Р)*3+ р"*+(р'+р3+рЧР+1/,
а (р"+рг+1) ^+(р=+р*+рл+рг+р +1 )*2+ (pHP2)xf(pS+P3).
¦ -
- X.
Таким образом, многочлен / (х) делит двучлен х64 - х и, следователь но,
имеет четыре различных корня в поле fe4- Рассмотрим
218
Гл. 4. Разложение многочленов на множители
| " "V >
теперь многочлен S (х) = х + х2 4- х4 + х* + х1' 4- х32. Из веденных выше
сравнений получаем, что
S (х) s (р5 + р3 I- р2 + р + 1) х3 + рвх2
+ (Р3 + Р2 + 1) (mod / (х)),
V* г
(р3 + ра) X +
%
так что

' Ч'
• .. № ¦Ф
НОД (/ (х), S (х))
НОД (/ (х), (р5 + р3 + р2 + р + 1) X8 + Р6Х2 + (Р3 + Р2) X + (Р3 + р2 +
1)) =
. Уу
L*
.JT1
X
Г + Ра + р3) ла + (Р5 + р2 •"!- 1) X + (р8 + Р2) - 8
" >
и
НОД (/ (х), S (х) - 1)
= НОД (/ (х), (ро + Р3 + Р2 + р +
f 1) X3 + р5Х2 + (р3 + Р2)Х + (р3 + = X + р3.
Р2)
Поэтому из (4.24)
получаем
/ (х) ¦ 8 (х) (X 4- Ря).
1 1
' &
у
гГ-
:'*М
5 <".1:4:'
. KV*-< ¦ V да..
т
ХМ'
Г-
\S.ii
:Hi
Чтобы найти корни многочлена g (х), мы теперь применим ра:
жение (4.25) с j - 1. Поскольку
S (рх) = рх + р2х3 + р4х4 + pV + р,9х16 + р32хю =
= рх + р2х2 + Р4х* + (р3 + р2) Xй +
+ Г + р + 1) Х1в + (Р3 -| 1) X32,
то нз полученных выше сравнений вытекает, что
S (Рх) ее (р2 + 1) х3 f (р3 + р + 1) х2 + (р5 + р4 + р3 +
-г р2 4- р + 1) х + (р4 + р2 -|- Р) (mod / (г)).'
Так как многочлен g (х) делит f (х), то это сравнение выполняете^ также и
по модулю g(x), поэтому
S (рх) = (р2 i 1) х3 4- Г + р 4- 1) х2 4- (Р8 !- р4 f Р3
+ Р2 + Р + 1) х 4- (р4 4- р3 4- р) =
ЕЕ Г н Р2) X3 4- р3х 4- (Р3 4- Р3 4- Р) (mod g(x)).
Таким образом,
НОД (g (х), S (рх)) =
'\Ь.
Ч
.
= НОД (g (х), (р8 .
4 (р8 + р3 4~ Р)) =
= х24-(Р8+ 1)х г (р4
р3) X2 4- р3х 4-
Р3 + Р2 + Р)
$'Л
х-'М
,' ч !'
• ArtV ..
5
. Vsv
я
НОД (g (х), S (рх) - 1)
НОД (g (х), (р5 4- р3) Xs + Р3Х +
+ (Р5 + Р8 + Р + 1)) =
х + (р4 + Р3 4- 1).
'Ч7|>
'cW
1 I
• П1
§ 3. Вычисление корней многочленов
219
Поэтому для / = 1 из (4.25) получаем, что
?(х) = А(х)(х+(Р4 + Р2 + !))• (4*27)
Чтобы найти корни многочлена h (х), снова применим разложение
(4.25), но возьмем / - 2. Поскольку
S (р2х) - р2х + р4х2 + Р8х4 + р 19х8 + Р32х16 4- P'V2 =
- р2х 4" Р4х2 4" (Р3 4" Р2) х* 4" (Р4 + р + 1) х3 4"
4- (Р3 4- 1) х1в 4- Рх32,
то такой же подсчет, как и для S (Рх), дает
5 (Р2х) = (Р5 4- Р2 + 1) Jf 4- (Р5 + Р3 + Р2) (mod h (х)).
Поэтому
НОД (А (х), 5 (р2х)) - НОД (h (х), Г + Р2 4- 1) х 4- Рв
+ рз + ра) =
- х 4" (Р 4~ 1)"
НОД (h (X), 5 (р2х) - 1) = НОД (h (х), (Р5 + р2 4- 1) X 4-
4- рв 4- р3 4- Р2 4- 1) =
= х 4- (Р3 4- р),
так что из (4.25) для j = 2 мы получаем
h (х) = (х 4- р + I) (х 4- р3 4- Р)* (4.28)
Объединяя (4.26), (4.27) и (4.28), получаем следующее разложение
многочлена /:
/ (х) = (X 4- Р 4- 1) (X + Р3 + Р) (х 4" Р4 + р2 4- 1) (X 4- Р5),
так что корнями многочлена f (х) в поле IF64 являются элементы
Р + 1, р3 + р, р4 4- Р2 4- 1 и р5. ?
И наконец, мы рассмотрим проблему отыскания корней многочлена для случая
большого конечного поля с большой характеристикой р. Как уже говорилось
раньше, достаточно выяснить, как находить корни многочленов вида
/(*)= П (*-т.)
i =1
с различными элементами уъ ..., у" ? Для выяснения вопроса, будет ли
данный многочлен f (х) иметь такой вид, достаточно лишь проверить
выполнение сравнения xQ = х (mod (/ (х)) (ср. с первой частью примера
4.16). Мы можем предположить, что q - наименьшая степень характеристики
р, для которой выполняется
220
Гл. 4. Разложение многочленов на множители
¦i?
те
это сравнение. Многочлен / (х) зададим стандартным предеть нием
х'-'Ж
п
№)
? ajx I,
/WO
"¦№
V>i
*yi
где "у ^ Fg для 0 с / < " и an !.
Нашей первой целью будет отыскание какого-нибудь нетр в на ль ного
делителя многочлена / (х). Чтобы исключить тривиа4 ный случай,
предположим, что п 2. Считая, что q ~ рт, смотрим многочлены
t-'i!
П
/=0
/г - 0, 1, . , m - 1
(4:
так что /0 (х) - / (х) и (х) - нормированный многочлен над для каждого к,
0 < к < т - 1. Нетрудно видеть, что для С 1 < г < л, и ky 0 < k < гп - 1,
П
ь (v?*) = s < V/
/~о
/\р*
S"/y!
/-0
-0,
так что
М*)
Я
П(*
iw_l
о
t />
WO, i,
m
1.
Построим теперь многочлен
¦ к,
¦¦ *%
.•:&Ц • Ti4.
•. b* 5
- W
m-I
F{X)=: П fh(x).
k-^a
&
Это многочлен над полем Fp> так как
(4
т-i п
F (х) - П П (х - у
к= 0 0-1
k
п №- 1
Г) = П П (х
t=I k^Q
к
п
vf)
П F, (x)m,dt
t=t
г. VF
.WSf.
. v'W
-W
где Ft (х) - минимальный многочлен элемента yt над полем а &х - его
Предыдущая << 1 .. 88 89 90 91 92 93 < 94 > 95 96 97 98 99 100 .. 371 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed