Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
получаем
qm2b~a ^ | _|_ ^2* ф 1 (mod 2ь+'),
откуда вытекает, что q^2b-a ф \ (mod et). Следовательно, мы должны иметь
d - m2b"°+I - m26"*4-if поскольку в этом случае k ¦- а. Поэтому формула d
- m2&"*+| = т/21-^ справедлива в обоих случаях.
Так как круговой многочлен Qet (jc) разлагается в произведение различных
нормированных неприводимых многочленов из Fg [х] степени mt2l~k, то и
каждый многочлен /у (.С) разлагается в произведение таких многочленов.
Сравнивая степени, получаем, что число таких сомножителей равно 2к~К
Поскольку каждый из указанных неприводимых сомножителей giS (х)
многочлена fj (х*) Делит Qet (х)у то каждый многочлен gu (лс) имеет
порядок et. Многочлены gij (лс) с различными наборами индексов (С /), 1 i
^ 2*-1,
* / ¦< N, различны, так как в противном случае один такой
Многочлен, скажем g (х), делил бы многочлены /д (л'О и /уг (*').
130
Гл. 3. Многочлены над конечными полями
•Ш
"ViuuV^I •
¦ *КчК-ММ*-л-р | | | I
u_ rsK-AX-^W-1
jw3F№vri • ча
где fa Ф /2, и тогда для любого корня р многочлена g (х) степень рт была
бы. общим корнем многочленов /д (г) и /щ (х), что невоз4| можно. По
теореме 3.5 число нормированных неприводимых многой членов степени
mt21'~k и порядка et в кольце |д \х] равно}
ср (et)imt2l~~h - 2ft-1tp (et)itni - 2й 1д {е)!т = 2к-лМ7 и, сдедовадр
тельно, многочленами gu (х) исчерпываются все такие много-1 члены. ' гА
¦ n"J N ?
Теперь мы покажем, как из данного неприводимого много*-! члена порядка е
получить все неприводимые многочлены, порядк".-| которых делят а.
Поскольку в их число обязательно войдет не<| приводимый многочлен g (х) =
х\ то мы будем рассматривать'! лишь те неприводимые многочлены g, для
которых g (0) Ф~0,1 Пусть / ---нормированный неприводимый многочлен из
f(.? Fxji степени т и порядка а, такой, что / (0) 0. Пусть а 4
г
ч
т
некоторый корень многочлена н для каждого t 4 im пусть gt 4 FT 1*1 -
минимальный многочлен элемента с4 над
Пусть Т " \(ъ in\ множество натуральных чисел, таких|
что для каждого i 4 41 существует однозначно определенны^ .индекс 4 1 -щ
i ¦< ^ такой, что i ж ipf (mod е) дли некоторого целого числа Ь >¦ 0.
Такое множество Т можно, например, шЩ строить следующим образом. Положим
4 - !, и, когда уж| построены tlt .4-1" пусть 4 будет наименьшим
натуральны^ числом, для которого ij ф. tiqb (mod е) при 1 ¦< i < j и все:
целых Ь >- 0, Эта процедура закончится через конечное числ шагов.
При введенных выше обозначениях получаем следующий "o|jj щий результат.
' iii
3.38. Теорема. Многочленами gtlt .gi" исчерпываются
различные нормированные неприводимые многочлены из Fg UI1 порядки которых
делят число о, а постоянные члены отличн от нуля,
.За
Доказательство, Каждый многочлен gt. по определению но. мирован и
неприводим в кольце Fg fx] и удовлетворяет условЩ gt, (0) ф 0, Кроме
того, раз многочлен gt. имеет корень aTg пор If док которого в группе
f,!m. делит порядок элемента а, то из те ремы 3.3 следует, что ord (gti)
делит е.
Пустьпроизвольный нормированный неприводимый мво член из Fg [at] порядка
d, делящего е, такой, что g (0) Ф 0. Ес р - какой-нибудь корень
многочлена g7 то из равенства -следует, что р- ¦ 4 так что р -
корень степени е из едини
над [|д, Так как а - первообразный корень степени е нз едини: над (F9, то
ез теоремы 2.42 (!) получаем, что р - а' для некоторой / N. Тогда из
определения множества Т следует, что i
§ 3. Построение неприводимых многочленов 131
• • . Г1ГГ 1.М-.-1Г-П1-.-1Г- II •
^ ttqb (mod е) при некотором целом i, 1 <; i п, и целом Ъ ^ 0.
Поэтому р - а* - (af()*\ так что р - корень многочлена gti
(согласно теореме 2.14). А поскольку g - минимальный многочлен элемента р
над Fg, нз теоремы 3.33 (iii) следует, что g = gti,
Остается показать, что многочлены gtr 1 < i <! п, различны. Допустим,
чтО?^ - gtf при i Ф /. Тогда а** и а*з - корни многочлена gt(i так что
afJ - (а^уь для некоторого Ь 0. Отсюда
следует, что tj = ttqb (mode), но так как, кроме того, = эн tjqn (mod е),
то мы получаем противоречие с определением множества Т. Q
Минимальный многочлен gt элемента а( ? Fgm над Fg обычно вычисляют с
помощью характеристического многочлена ft этого элемента надРсг Из
рассуждения, следующего за определением
2.22, мы знаем, что ft = gu, гДе г = м/й и к -степень многочлена gt.
Поскольку многочлен gt неприводим в кольце Fg [х], число к является
показателем, которому принадлежит q по модулю d = ord (gf); поэтому число
d равно порядку элемента а( в группе а этот порядок по теореме 1.15 (ii)
равен е/НОД (/, е), Значит, число d, а также k и г можно легко
определить.
Для вычисления характеристического многочлена ft элемента а* ? Fgm над Fq
существует несколько способов. Одни из них основан на использовании связи
между многочленом /( и исходным многочленом /.
3.39. Теорема. Пусть f - нормированный неприводимый много-член степени т
из Fg ЕjcJ. Пусть а ? Fgm - какой-либо корень того многочлена, и для t ?
IN пусть ft - характеристический лтогочлен элемента а* ? Fgm над Fg.
