Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
итФ Он Sid) = D{d) - I- единичные ма-трицы соответствующего порядка.
Сравнение матричных коэффициентов при высших степенях переменной х в
обеих частях равенства = UD^E дает / = UMIE, так что т ~ 0. Поэтому и ^
U0 = ?-1 и SW = E~~]D<d>E.
Сравнивая матричные коэффициенты при одинаковых степенях переменной х в
последнем равенстве, получаем Srrf) - E~{D{d)E Для всех г, 0 < г < d.
Следовательно, матрицы Srd) и D{d) имеют
210
Гл. 4. Разложение многочленов и а множители
.5 *
- \\>у
о "кЛ
одинаковые характеристические многочлены, а значит, и одияа
вые собственные значения; кроме того, поскольку D(rd) ~~ нальная матрица,
то ее собственные значения совпадают с ее
тональными элементами. Поэтому эти диагональные элеме! можно найти как
корнн характеристического многочлена матр^
S^d), причем все они должны принадлежать полю Г?. Таким об зом, мы снова,
как и в предыдущих способах, сводим пробд разложения многочлена f к
задаче отыскания корней некотор многочленов в поле Fg.
Частичное разложение (4Л6} можно получить также со другим способом.
Расширим определение многочленов^, обш чая через gif i 1, произведение
всех нормированных вепри днмых многочленов степени i из Fg [хЗ, которые
делят мно член /. В частности, (х) - 1 а том случае, если многочлен! не
имеет в кольце Fg [хЗ неприводимых делителей степени; Тогда мы можем
написать
f= П gt.
i >1
4
ы
. * t . _
j'.fV.
Л5/'
Ясно, что нужно рассматривать лишь те значения г, которые превосходят deg
(/). Будем теперь, исходя из равенств
Г" (х) = х, F" (х) = / (х),
последовательно находить многочлены га (х), гх (х), а та F0 (х), Fx (х),
... и dt (х), d2 (х), используя для i ^ 1 щие рекуррентные соотношения;
rt (х) ее rui (xf (mod Ft.i (*))> deg (rt) < deg (F^),
di (x) = НОД (F*_l (x), rt (x) - x},
Ft (x) - Ft_i (x)/di (x).
Этот процесс заканчивается, когда di (х) = F#_x (х).
4.13. Теорема, В обозначениях, введенных выше, для всех i имеет место
равенство dt (х) - gt (х).
Доказательство. Учитывая делимость многочлена FU1 на прямой индукцией
получаем, что
At!
ш
Щ
; I;,*'
¦At
ь
rt (х) ее jA1 (mod F/_x (*)) Для всех i > 1. Докажем теперь при помощи
индукции, что
Ft-i = П gj и d, = gt для всех I > 1.
I?1
При i - 1 первое равенство выполняется, поскольку F<> касается второго
равенства, то в силу (4Л7)
dL (х) - НОД (F0 (х), гх (х) - х) = НОД (/ (х), х* -
(4.1
(4
X}
§ 2. Разложение многочленов над большими конечными полями
211
и поскольку двучлен х? - х равен произведению всех нормированных линейных
многочленов из кольца Fg lx], то многочлен dx является произведением всех
нормированных линейных многочленов из Fg UK которые делят /, так что dx -
gx. Теперь предположим, что равенства (4.18) выполняются для некоторого г
1. Тогда
Ft = Fuiidi = Futlgi = П gJr (4Л 9)
)>i+l
так что первое равенство из (4Л8) доказано для г-f 1. Кроме того, из
(4Л7) получаем
dui W = Н°Д (О W. rui (*) -*) = НОД (F, (x), x" - x).
%
i J-f
В силу теоремы 3.20 двучлен xq - х является произведением всех
нормированных неприводимых многочленов из Fg [лс], степени которых делят
число i + 1. Поэтому многочлен di+1 является произведением всех
нормированных неприводимых многочленов из Fg lx], которые делят Ft и
степени которых делят i -f 1. Из (4 Л 9) тогда следует, что di+1 = gi+1.
?
В изложенном алгоритме самым сложным шагом (с вычислительной точки
зрения) является нахождение многочлена г, путем
приведения многочлена г?_! по модулю F(_v. Общая техника сокращения
вычислительной работы при этом основана на предварительном нахождении
вычетов по модулю многочленов
*7-i, ь t\-i (где 2е - наибольшая степень двойки, не превосходящая q)
последовательным возведением в квадрат и приведением по модулю РЫ1 с
последующим перемножением того набора
полученных вычетов, который дает нужную нам степень многочлена ги1 по
модулю Ри1. Например, чтобы получить вычет
степени rft\ по модулю нужно перемножить вычеты степеней
rJii, r?__i и г/ I по модулю F(_[.
Однако вместо техники повторных возведений в квадрат мы могли бы для
нахождения многочлена (*) по известному ги1 (*) использовать матрицу В из
алгоритма Берлекэмпа (см. § 1). Пусть п = deg (f) н
(х) = 2
/-О
Определим вектор (sS°\ s*1*, -.., I)) f fna матричным равен-
ством
W°\ s\\ ... , srJ)) - r\llu . . rfc0) B, (4.20)
14*
212 Гл. 4. Разложение многочленов на множители
. . . ________________________
где В - матрица порядка п из (4.5). Если ввести многочлен
л-!
М*) == S sl-'V, (4.21)
/=о
то получим, что rM (х)<* = Si (х) (mod / (я)), откуда г("х (х)* н. Sj
(лг) (mod Fi_1 (х)), так что
п (X) гг St (х) (mod FU1 (х)).
Поэтому если известна матрица В, то на каждом шаге I мы, зная многочлен
rt_x (х), можем найти многочлен rt (х) приведением по, модулю F^x (х)
многочленов $t (х), получаемых из (4.20) и (4.21).;
4.14. Пример. Рассмотрим тот же многочлен / (х) - Xе-¦ ¦
- Зх5 + 5х4 - 9х3 - 5х3 + бх + 7 С Р2з U1, что и в примере
4.7. Тогда матрица В имеет вид
