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

UptoLike

ВУЗ: 

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

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

Рубрика: 

5.6 Расширенный алгоритм для полиномов над полем
Алгоритм Ext_Euclid_P
Вход:
р
1
(х), р
2
(х)
∈
I[x], поле - 0
212
I;n)x(p^)x(p^m,)x(p =≥
=
≠
.
Выход:
).x(f)x(p)x(q)x(p)]x(p),x(p[)x(p
),x(p^)x(p^)x(q^),x(p^)x(p^)x(f:^)x(I)x(q),x(f),x(p
h
hh
2121
221
НОД +==
−
<
−
<
∈
Шаги алгоритма
{Инициализация}
[p
0
(x), p
1
(x)]:= [p
1
(x), p
2
(x)];
[q
0
(x), q
1
(x)]:=(1,0); [f
0
(x),fq
1
(x)]:=(0,1)
{Основной цикл} Пока
0
1
≠
)x(p
выполнять
q(x):=POF [p
0
(x), p
1
(x)]
[p
0
(x), p
1
(x)]:= [p
1
(x), p
0
(x) - p
1
(x)q(x)]
[q
0
(x), q
1
(x)]:=[q
1
(x), q
0
(x) - q
1
(x)q(x)]
[f
0
(x), f
1
(x)]:= [f
1
(x), f
0
(x) - f
1
(x)q(x)]
3 {Выход} Вернуть )]x(f),x(q)x(p[:)]x(f),x(q),x(p[
h 000
=
Пример – Пусть 251247
3
2
35
1
+=+++= x)x(p,xxx)x(p полиномы над
полем
Z
11
. Тогда расширенный алгоритм Евклида дает таблицу 5.2
Таблица 5.1
Фун-
кция
Итерация
0
1 2 3 4
q(x) - 8x
2
+3 10x+4 8x+10 7x
p
0
(x) 7x
5
+4x
3
+2x
+1
5
x
3
+2 6x
2
+2x+6 9x 6
p
1
(x) 5x
3
+2 6x
2
+2x+6 9x 6 0
q
0
(x)
1 0 1 x+7 3x
2
+8
q
1
(x)
0 1 x+7 3x
2
+8 -
f
0
(x) 0 1 3x
2
+8 3x
3
+10x
2
+8x+
1
9x
4
+4x
2
+3x+1
0
f
1
(x) 1 3x
2
+8 3x
3
+10x
2
+8x
+1
9
x
4
+4x
2
+3x+1
0
Проверка: (7
x
5
+4x
3
+2x+1)(3x
2
+8)+(5x
3
+2)(9x
4
+4x
2
+3x+10)=6.
Ответ, который дает алгоритм, есть 6. Как ранее отмечалось, лучше в
качестве ответа взять нормированный полином (разделить на старший коэффи-
циент) и его назвать наибольшим общим делителем данных двух полиномов
Ответ:
НОД [p
1
(x), p
2
(x)]=1. 
        5.6 Расширенный алгоритм для полиномов над полем

        Алгоритм Ext_Euclid_P
        Вход: р1(х), р2(х) ∈ I[x], p2 ( x ) ≠ 0, m =^ p1( x ) ≥^ p2 ( x ) = n; I - поле .
        Выход:
        ph ( x ), f ( x ), q( x ) ∈ I ( x ) :^ f ( x ) <^ p1( x )−^ p2 ( x ), ^ q( x ) <^ p2 ( x )−^ ph ( x ),
       ph ( x ) = НОД [ p1( x ), p2 ( x )] = p1( x )q( x ) + p2 ( x ) f ( x ).
Шаги алгоритма
      {Инициализация} [p0(x), p1(x)]:= [p1(x), p2(x)];
      [q0(x), q1(x)]:=(1,0); [f0(x),fq1(x)]:=(0,1)
      {Основной цикл} Пока p1( x ) ≠ 0 выполнять
      q(x):=POF [p0(x), p1(x)]
      [p0(x), p1(x)]:= [p1(x), p0(x) - p1(x)q(x)]
      [q0(x), q1(x)]:=[q1(x), q0(x) - q1(x)q(x)]
      [f0(x), f1(x)]:= [f1(x), f0(x) - f1(x)q(x)]
      3 {Выход} Вернуть [ ph ( x ), q( x ), f ( x )] := [ p0 ( x ) q0 ( x ), f 0 ( x )]
      Пример – Пусть p1( x ) = 7 x 5 + 4 x 3 + 2 x + 1, p2 ( x ) = 5 x 3 + 2 полиномы над
полем Z11. Тогда расширенный алгоритм Евклида дает таблицу 5.2

        Таблица 5.1

Фун-      Итерация
кция
         0                 1               2                  3                    4
q(x)     -                 8x2+3           10x+4              8x+10                7x
p0(x)    7x5+4x3+2x        5x3+2           6x2+2x+6           9x                   6
         +1
p1(x)    5x3+2             6x2+2x+6        9x                 6                    0
q0(x)    1                 0               1                  x+7                  3x2+8

q1(x)     0                1               x+7                3x2+8                -

f0(x)     0                1               3x2+8       3x3+10x2+8x+ 9x4+4x2+3x+1
                                                       1            0
f1(x)     1                3x2+8             3    2      4   2
                                           3x +10x +8x 9x +4x +3x+1
                                           +1          0

       Проверка: (7x5+4x3+2x+1)(3x2+8)+(5x3+2)(9x4+4x2+3x+10)=6.
       Ответ, который дает алгоритм, есть 6. Как ранее отмечалось, лучше в
качестве ответа взять нормированный полином (разделить на старший коэффи-
циент) и его назвать наибольшим общим делителем данных двух полиномов
Ответ: НОД [p1(x), p2(x)]=1.

Страницы