Составители:
Рубрика:
Равенство (3.9) показывает, что произведение некратных сомно-
жителей можно получить не выходя из кольца R[x], ибо его левая
часть получается лишь операциями дифференцирования многочле-
на из R[x], отыскания НОД двух многочленов из R[x] и деления
многочленов из R[x].
Заметим также, что в процессе вычислений получено произве-
дение R(x) кратных сомножителей многочлена P (x) в степенях на
единицу меньших, чем в многочлене P (x) (см. формулу (3.6)). Ес-
ли теперь в предыдущих рассуждениях заменить P (x) на R(x),
то аналогично (3.9) мы найдем произведение P
(2)
(x) сомножителей
(в первых степенях) многочлена P (x) с кратностью два, причём
опять-таки это произведение будет получено без выхода из кольца
R[x].
Аналогичным образом получаются все произведения P
(j)
(x), j =
1, 2, . . . , max
i=1,...,n
n
j
, без выхода из кольца R[x], что и требовалось.
Итак, не выходя из кольца R[x], можно получить представление
многочлена P (x) в виде (3.3), где у каждого многочлена P
(j)
(x) нет
кратных сомножителей.
Представление (3.3) называется разложением многочлена P (x)
на свободные от квадратов множители.
Ассимптотически сложность разложения многочлена P (x) на
свободные от квадратов множители имеют тот же порядок,что и
сложность вычисления НОД (правда алгоритм, предложенный вы-
ше, придётся модифицировать).
4. Расширенный алгоритм Евклида
Евклидов алгоритм вычисления НОД двух целых чисел q и r
имеет вид
1) begin
2) if abs(q) < abs(r) then
3) begin
4) t:=q;
5) q:=r;
6) r:=t;
7) end; { перестановка q и r }
8) until r 6= 0 do
9) begin
86
Страницы
- « первая
- ‹ предыдущая
- …
- 83
- 84
- 85
- 86
- 87
- …
- следующая ›
- последняя »
