Математические основы криптологии. Галуев Г.А. - 18 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

35
Наибольший общий делитель двух многочленов (также как
и двух целых чисел) можно найти при помощи алгоритма Евк-
лида. Пусть многочлен
g(x)
≠
0 и не делит многочлен f(x).
Тогда, применяя многократно алгоритм деления многочле-
нов с остатком, получим
11 1
21 2 2 1
1323 3 2
21
( ) ( ) ( ) ( ) 0 deg( ( )) deg( ( ))
() ()() () 0 deg( ()) deg(())
() () () () 0 deg( ()) deg( ())
() () () () 0 deg(
SSSS S
fx g xgx rx rx gx
gx g xrx rx rx rx
rx g xrx rx rx rx
rxgxrxrx r
−−
=+≤<
=+ ≤<
=+≤<
•
•
•
=+≤
1
11
()) deg( ())
() () ()
S
SSS
x
rx
rxg xrx
−
−+
<
=
Т.к. степень
deg(g(x)) конечна, то процедура заканчивается
за конечное число шагов. Если старший коэффициент последне-
го ненулевого остатка
)(xr
S
равен b, то
)())(),((
1
xrbxgxfНОД
S
−
=
.
Если у нас более чем 2 многочлена
(n>2), то
НОД( )(),...,(
1
xfxf
n
) при ненулевых многочленах
)(),...,(
1
xfxf
n
находят (как и для целых чисел), применяя рас-
ширенный алгоритм Евклида: сначала определяют
НОД( )(),(
21
xfxf ), а затем находят последовательно, применяя
алгоритм Евклида,
НОД(НОД( )(),(),(
321
xfxfxf ))=НОД( )(),(),(
321
xfxfxf ) и
т.д.
Пример:
xxxxg
xxxxf
++=
+++=
24
236
)(
1)(
Найдем
НОД( )(),(
x
g
x
f
) по алгоритму Евклида
1)1(1
1)1()1(
1)()1(1
2324
242236
⋅+=+
++⋅++=++
++++⋅+=+++
xx
xxxxxx
xxxxxxxx
36
Значит,
НОД( )(),(
x
g
x
f
)=1 т.е. многочлены f(x) и g(x)
взаимно простые.
Двойственным к понятию
НОД является понятие наи-
меньшего общего кратного. Пусть )(),...,(
1
xfxf
n
- ненулевые
многочлены. Тогда можно показать, что существует однозначно
определенный нормированный многочлен
m(x), обладающий
следующими свойствами:
1.
m(x) делится на каждый многочлен
) ,...,1), (( nixf
i
=
;
2. любой многочлен
g(x), который делится на каждый из
многочленов
) ,...,1), (( nixf
i
=
делится на m(x).
Многочлен
m(x) называют наименьшим общим кратным
многочленов
)(),...,(
1
xfxf
n
и обозначается
НОК )(),...,(
1
xfxf
n
. Для двух многочленов
0)( 0)(
≠
≠
x
gи
x
имеет место соотношение
))(),(())(),(()()(
1
xgxfНОКxgxfНОДxgxfa =⋅⋅
−
,
где а - старший коэффициент произведения
f(x) и g(x).
Важнейшим понятием теории чисел является понятие не-
приводимого многочлена. Многочлен
f(x) называется неприво-
димым, если он имеет положительную степень и равенство
f(x)=g(x)h(x) может выполняться лишь в том случае, когда либо
g(x), либо h(x) является постоянным многочленом (т.е. его сте-
пень
0
≤
n ). Другими словами, многочлен f(x) является непри-
водимым, если он допускает только тривиальные разложения на
множители.
Многочлен положительной степени
f(x) называется приво-
димым, если существуют два многочлена положительной степе-
ни
)( ) (
21
xfиxf такие, что )()()(
21
xfxfxf
⋅
=
, т.е. если
этот многочлен
f(x) не является неприводимым.
Неприводимые многочлены играют важную роль в теории
чисел, так как любой многочлен
f(x) может быть записан, при-
чем единственным способом, в виде произведения неприводи-
мых многочленов (аналог того, что любое число
n>1 может быть
представлено в виде произведения простых чисел).

Страницы