Математическая логика и теория алгоритмов. Стенюшкина В.А. - 96 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

Рассмотренный алгоритм можно применить к вычислению обратного
полинома для данного полинома
p(x)
≠
0 в Z
p
[x]
m(x)
, где
∧
p(x)<
∧
m(x), p-простое
число,
m(x)-непрерывный полином в Z
p
[x]. Действительно, применяем алгоритм
Ext_Euclid_P к m(x) и p(x); получаем полиномы f(x) и g(x), для которых
m(x)f(x)+p(x)g(x)=1.
Затем, вычисляем значение в точке
α
=[x]
m(x)
,m(
α
)=0; получается
p(
α
)g(
α
)=1 в Z
p
[x]
m(x)
, то есть p(
α
) обратим Z
p
[x]
m(x)
. 
       Рассмотренный алгоритм можно применить к вычислению обратного
полинома для данного полинома p(x)≠0 в Zp[x]m(x), где ∧p(x)< ∧m(x), p-простое
число, m(x)-непрерывный полином в Zp[x]. Действительно, применяем алгоритм
Ext_Euclid_P к m(x) и p(x); получаем полиномы f(x) и g(x), для которых
m(x)f(x)+p(x)g(x)=1.
       Затем, вычисляем значение в точке α=[x]m(x),m(α)=0; получается
p(α)g(α)=1 в Zp[x]m(x), то есть p(α) обратим Zp[x]m(x).

Страницы