Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
Тогда для любого k-набора (сь элементов поля Fg, согласно
китайской тео-
Реме об остатках, существует единственный многочлен к ? € Fg lx], такой,
что к (х) = ct (mod Д (х)), 1 и deg (к) <
< deg (/), Этот многочлен удовлетворяет условию
к (xf ~ с? = Ci = h (х) (mod ft (х)), i ~ 1 k>
190
Гл. 4. Разложение многочленов на множителя
. wm
и потому
¦и
№ ~ &(mod /), deg (h) < deg (/).
(4г
С другой стороны, если многочлен к является решением сравш ння (4.3), то
из равенства
К (хе - h (х)
П (Л(х)-<?)
с ? jp
Я
¦
ШР
•..й'Г
* ч<4
1'li 4 • •%
¦лщ
в силу попарной взаимной простоты сомножителей правой ча следует, что
каждый неприводимый делитель многочлена f до*|| жен делить один и только
один из многочленов к (х) - с. Таки образом, каждое решение к (х), deg
(к) < deg (/), сравнения (4>| удовлетворяет системе сравнений к (х) в с*
(mod ft (х)), i ¦?
- 1, к, для некоторого А-набора (с1( с*) элементов поля f
Следовательно, сравнение (4.3) имеет ровно qk решений.
Чтобы найти эти решения, сведем сравнение (4.3) к систе линейных
уравнений. Полагая deg (f) = п н вычисляя xii} по дулю f (х), построим п
хп-матрицу В ^ (Ьи), 0 < i, /< п -А именно -.р
П-I
х1'9 = ? btjxf (mod f (х)), i ~ 0, 1, ..., п - 1. (4
>=о
.. ш
j
а
t-r#
6:*ij
Тогда многочлен к (х) = ай + агх -f... + ап_1хл"1 С Fg [х] бу решением
сравнения (4.3) в том и только том случае, когда \ alf an-1) является
решением системы линейных уравней (записанной в матричной форме)
(а0, аъ .. ., апД)В = (а0) аь . . an_i). (4
: !:
А
• • 'Ц'И*:?
•А?
"
Это следует из того факта, что равенство (4.5) выполняется тощ н только
тогда, когда
safes
А *. ?!.
.УМ"!-
к{х)
tl-\
ух -! л-I
aj*f = ? ? <*tbifXl =
/-О /-О Ь=0
П- \
? atx^ = fc(x)*(mod/(x)).
о
'
i; :Дщ;
¦
. ¦¦ ЩА . :
¦¦Мчг
ч V ч *
• '
I • . O'. V
*5 •
Систему (4.5) можно записать в следующей эквивалентной
(а0, аъ . ... an_i)(S -/) = (0, 0, ..., 0),
й*г1|
(4д
А'* 'Д
где / - единичная нХя-матрида над Fa. Согласно доказанной выше,
однородная система (4.6) имеет qk решений. Это означав; что размерность
пространства решений *) этой системы равна
п.?*
>•?*
х) Это пространство называют также аннулируемым пространством
матрицы В - - /7/шж. ле/до. "
д;
' • дш
§ {. Разложение многочленов над малыми конечными полями 191
т е числу различных нормированных неприводимых делителей
многочлена /, а ранг матрицы В-/ решен п - k.
Поскольку постоянный многочлен ht (х) = 1 всегда является решением
сравнения (4.3), то соответствующий ему вектор (I, О, всегда является
решением системы (4.6), в чем можно
убедиться также н прямой подстановкой. Кроме того, найдутся еще
непостоянные многочлены ft2(x), /гй (х) со степенями, не превосходящими
п- 1, такие, что соответствующие им и мнбго-члену hi (х) векторы образуют
базис пространства решений однородной системы (4.6). Поскольку все
многочлены /t2 (х) /tA (х)
непостоянны и удовлетворяют сравнению (4.3), то они являются /-
разлагающими многочленами.
При таком подходе важную роль играет отыскание ранга г матрицы В-/. Как
было отмечено выше, г - п - к; поэтому, найдя ранг г, мы тем самым
находим число к ^ п - г различных нормированных неприводимых делителей
многочлена /. А это позволяет судить о том, до каких пор нужно продолжать
процедуру разложения.
Ранг матрицы В - / обычно определяется приведением этой матрицы к
ступенчатому виду с помощью элементарных преобразований ее строк и
столбцов. Одна ко, поскольку мы хотим в то же время решить систему (4.6),
целесообразно применять лишь преобразования столбцов, поскольку
пространство решений этой однородной системы нивариаитно относительно
таких преобразований. Итак, мы допускаем следующие элементарные операции:
перемена местами двух столбцов матрицы В - /, умножение любого ее столбца
на ненулевой элемент поля fq и прибавление к любому ее столбцу другого
столбца, умноженного на любой элемент из fq. Ранг г матрицы В - / - это
число ненулевых столбцов полученной матрицы ступенчатого вида.
Вычислив г, мы найдем число к = п - г. Если к = 1, то мы заключаем, что /
- неприводимый многочлен иад [F?} и процедура на этом заканчивается. В
этом случае едниствеиными решениями сравнения (4.3) являются постоянные
многочлены, и пространство решений системы (4.6) состоит лишь из векторов
вида (с, 0, ..., 0), где с ? [р?1 Если же к ^ 2, то мы берем /-
разлагающий базисный многочлен h% (х) и находим наибольшие общие делители
НОД (/ (х), вг (х) - с) для всех с ? Fq. В результате получим некоторое
нетривиальное разложение многочлена / (х), даваемое формулой (4.2). Если
использование многочлена h2 (х) еще ие приводит к разложению многочлена /
на к сомножителей, то переедим к следующему /-разлагающему базисному
многочлену /t3 (х) и находим НОД (g (х), /г3 (х) - с) для всех с ? (Fg и
всех нетривиальных делителей g (х) многочлена / (х), найденных по формуле
(4.2) на первом этапе. Эта процедура продолжается до тех пор,
192
Гл. 4. Разложение многочленов на множители
