Вестник ДГТУ, 2007. Т.7. №3(34)
МАТЕМАТИКА
УДК 512.622
А.Э. МАЕВСКИЙ
АЛГОРИТМ ПОИСКА КОРНЕЙ МНОГОЧЛЕНОВ
С КОЭФФИЦИЕНТАМИ ИЗ КОЛЬЦА k[
, ]
Введение и постановка задачи. Пусть k – поле произвольной характеристики,
k[
ми из k, k[ , ][
, ] – кольцо многочленов от переменных
] (≅k[ ,
,
(
-
(∈k[ , ]) будем понимать максимальную из степеней мономов, входящих в
) (∈k[ , ][
симальный показатель степени переменной
( ,
( ,
эффициентами из k[ , ]. Под
( , ), а под
,
,
(∈k[ , ][
полной степени не выше
( ,
) многочлена
, ( , )) нулевой.
deg( ( , )) многочлена ( , )
( ,
,
). Многочлен ( , ) (∈k[ , ]) будем называть
), если многочлен
Рассмотрим следующую задачу: для заданного многочлена
]) и заданного целого числа
(>0) найти все
-корни
, с которым она входит в
многочлена
( ,
( ,
,
,
)
)
. Эта задача возникает во многих областях современной
математики, например, в теории помехоустойчивого кодирования
при решении задач списочного декодирования [1], [2], [5]. Легко показать,
что множество
Ω
однозначном соответствии с множеством делителей
(
( , )), где deg( ( , )) ≤ . Поэтому исходная задача эквивалентна задаче
поиска всех линейных делителей многочлена
deg( ( , )) ≤ .
всех
-
( ,
,
) вида (
-
) вида
( , )),
Существует несколько подходов к решению поставленной задачи.
) может иметь большое количество ненужных нам линейных делителей
вида ( ( , ) + ( , )). В работе [5] предложен алгоритм поиска
-корней многочленов с коэффициентами из поля рациональных функций
k( 1,…,x ). Так как k[ 1, 2]⊂k( 1,…,x ) при
,
263
Например, можно использовать общие алгоритмы факторизации многочленов
от нескольких переменных [3], [4], и выделить все искомые линейные
делители специального вида. Однако вычислительная сложность при этом
может оказаться слишком высокой, так как почти все алгоритмы факторизации
многочленов от нескольких переменных вероятностные, а многочлен
( ,
≥ 2, этот алгоритм может быть
применен и для построения множества Ω ( ). Однако он использует нетри-корней
(
) = { ( , ) ∈ k[ , ] | deg( ( , )) ≤ ,
( ,
,
( ,
) полной степени не выше
находится во взаимно
( ,
, ( , )) ≡ 0 }
,
]) – мак,
])
– кольцо многочленов от переменной
с коэффициентас
коx
y
П
но н т п р н л н
с о о о т
т
о
м ее е а ц ы в
мк р и
и а ф в о
о ю ч
к ф е н
о
к л г К о
м
н
л
с и е ,
э ч е
р й с к о а и а ы
е
н д э и е и
л си т а о е
п е с и
н р м в й
л
е ф а н к р е
о м н з : к ео д
т ф л и о н л
н
м и ы л ц
е и ь е а ь
р ц н
о м м м н ч к
и е е в р [ о л
р а е т ] о ,
н ни т р и x г и
в
а и и н о л н е
н
н
й а л
е
о
г а м т
л и и
о k н е
x
x y
x
f
x
x
y
y
y T
y
x
с
Q x
Q
x y
y T
T
x
т
T
y
е
п
е
н
ь
ю
п
T
о
ы з к ю и е к н о о
л ь
о а k о
р
у т у о ч
н а Р с е н
а ч в н
а л о
т x т е л Р
г ц м н г и я
- аР йу м г пл е, аы
и [ с т ч м
к ш о т .
м п ] уy ю с
о , ги д л
с
а к
, н й е о
е о р л
к е k – пн р и и м о е н
з
о
р
е ой м в
о 2
н н то ав -
с с ф ш
н о э е
ж] п о к к у
а [ с Р
т к и т
о и ф н
и
а к и йц е
н а
о нч о т р н з о
о л ж е м а
н о о р н а
л
а о k и
т , ф
с г [
x
л
с
н
т
о
е
f
й
п
с
е
н
т
ь
е
п
ю
x Qy x
x x
f
y
d
x
y
T
Q
T
T
f
f
d Q
x
y
f
x
y
g
Q
x
y
T
m
T x
x
y
x T
y
y
x
f
d
T
f
x
y
x
x
x
x
y
m
m
Q
d
y
d
f
y y
d
x
y
d
е
н
ь
ю
y
f
x
y
Q
x
T
y
T
о л ае т л y ц
е е п с о x з
г ь е й м и ти к
в о . А и н . я
н о м ч , а
о о т в с
д л в о
н г а
й п и ср ь
е т я
р м
е
-
р е ] и
р
T x
f
x
T
-
y
к
y
T
о
р
н
е
м
T
Q d
x
Q
y
f
x
y
Q
x
y
x
T
y
T
T
f
x
y
Q x
Q
x y
y T
T
Стр.1