Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
стороны, согласно следствию 3.79, трехчлен g (ж) неприводим над Fp, так
что
§ б. Двучлены н трехчлены
167
Сравнение постоянных членов приводит к равенству р(рр"1)/(р-*) = 1,
откуда по теореме 3.3 следует, что порядок
многочлена g (х) = хр - х - 1 равен (рр - 1 )f(p - 1).
Обратно, если выполнены условия теоремы, то элементы а н р имеют в
мультипликативной группе порядки р - 1
и (рр - ЦКр- 0 соответственно. Далее,
\р - I )f(p - 1) = I + р + р2+ ... + рр~1 =
= I -{- 1 ~|- 1 -I(tm)* ",. -|- 1_
- р 1 (mod (р - I)),
так что числа р - I и {рр - 1 )1(р - I) взаимно просты.
Поэтому
элемента = а$ имеет порядок (р - 1)*(/?р - 1 )!{р - I) - рр - I в группе
f *р. Следовательно, а - примитивный элемент поля Fpj>,
а значит, / (х) - примитивный многочлен иад Fp- ?
3.85, Пример. Для р = 5 мы имеем (рр - !)/(/? - 1) - 781 = ~ П-71. Из
доказательства теоремы 3.84 следует, что х781 (tm)
^ ! (mod (х5 - х - I)), и так как х11 Ф I (mod (Xs - х - I)) и х71 Ф 1
(mod (хБ - х - I)), то получаем, что ord (х5 - х - I) =
781. Далее, числа 2 и 3 являются примитивными элементами поля lF5,
поэтому, согласно теореме 3.84, трехчлены х5 - х - 2
и х5 - х - 3 являются примитивными многочленами иад по-
лем F5.
Нетрудно видеть, что квадратный трехчлен х2 + х + а над полем fg нечетной
характеристики является неприводимым в кольце F<| [х ] в том и только том
случае, если элемент а ие представим в виде а = 4"1 - 52 ни для какого b
С Fq- Следовательно, существует (д - 1)/2 различных выборов элемента а С
F<|, для которых квадратный трехчлен х2 + х + а неприводим иад И вообще
число элементов а С для которых трехчлен хп + 4~ х f а неприводим иад
.fe, как правило, асимптотически равно qin согласно следующему
результату.
3.86. Теорема. Пусть характеристика р конечного поля Fg не делит числа 2п
(п - 1), где п ? N , п > 2, " пусть число элементов а ? F<i" для которых
трехчлен хп + х + а неприводим над равно Тп (q). Тогда существует
константа Bnt зависящая лишь от п, такая, что
Тп (?) - -F | < Vq.
Доказательство этой теоремы, опирающееся иа тонкое исследование некоторых
групп Галуа, мы опускаем.
В определении 1.92 было введено понятие дискриминанта многочлена. Ниже
устанавливается точная формула для дискриминанта трехчлена.
168 Гл. 3. Многочлены над конечными полями
- ,-|b'i'Ти'111 k-Vi 1 V -*lwm : ¦j:¦ ;i^i ^цм;! • •; ;u> ¦*** if1^^
• мй .sic
.У-АЧ #
,{i'i
%
•|-:Й
3.87. Теорема, Дискриминант, трехчлена хп -f axk + h ? J С: Fq Ijc ), где
п > к !> 1, выражается формулой
D (xn -j(tm) &хк + Щ ( -1)я<я~'!>/й6*-1 •
-[nNbN-'K ( 1)Л' (п ..
edc d - НОД (я, A), N = n/d, К ~ kid,
Комментарии
§ L Разнообразный материал о многочленах над конечными! полями можно
найти в монографиях Albert 13, ch., 5J и Berle kamp [4 j, а также в
вышедших совеем недавно книгах Blake,;]
Miiilin !i ], MaeWilHams, Sloane [2] и McDonald [I ]. Результаты/'
содержащиеся в этих книгах, имеют отношение ко всем параграф фам этой
главы. Дальнейшие результаты о многочленах и некоД торые дополнительные
ссылки на материал, выходящий за рамки, нашей книги, будут приведены в
конце комментариев к § 5.
Основные результаты, содержащиеся в лемме ЗЛ и следствии]! 3.4, был и до
к азан ы еще Г а у ее о м (G a u ss [41), И з учен и с п о р я д к%|
многочлена было продолжено Сер ре (Serret (31) и Пелле (Pely let 111), в
последней статье можно найти теорему 3.5; см. такжД Bachmanп [4, ch. 7] и
Dickson [7, part I, eh, 3], О теоремах 3.|fc и 8.9 см., например, Ward
[5]. Простой метод определения ord (Щ для неприводимого над простым полем
Гр многочлена [ степени лЦ в случае, когда (рт - \}/(р - 1) (tm) простое
число, предложен" Гараковым в 12 1. Как-уже отмечалось в основном тексте,
порядок) многочлена (см. определение 3.2) иногда называют также перио дом
(Berlekamp [4]) или экспонентой (Albert [3], Dickson 171 этого
многочлена. Понятие порядка многочлена от нескольких! переменных было
введено Лонгом (Long II1, 12 ])> Для миогочлеС на f (х) над fq,
удовлетворяющего условию f (0) Ф- 0, наименьшей натуральное число е,
такое, что f (х) делит двучлен хе - с при некотором с С Fq. называется
приведемным порядком этого многей члена; его называют еще интегральным
порядком. (Bose, С howl а Я а о U ]) н л и субэкстнентой (Н irsсhfеid
[41, [5]) многочлена / (x) Связь между порядком и приведенным порядком
неприводимого многочлена неявно указана в статье Ward [6 ]; ер. также с
леммо;
8Л7.
Таблицы неприводимых многочленов и их порядков имеются,'^ например, в
следующих работах: Chang, Godwin (1 ], Golomb * [4, ch. 31, Marsh fl ] и
McElieee 13] (см. также гл. 10 этой книги). Ключевым моментом при
отыскании порядков неприводимых многочленов является разложение на
множители чисел вида qm - 1. Укажем некот оры е и ст оч ники, где можно
найти такие разложения Классические таблицы таких разложений имеются в
работа*-* Cunningham, Woodall fl J, Cunningham [I] и Kraitchik [ 11
/5h
fj
tf;4,
Ш
ж-р ¦y%
