Презентация на тему Полиномы от одной переменной. Нохождение НОД. (Лекция 5.2)

образом, НОД(w5,v5)=х+2.

НОД(a,b) полиномов a и b, то степень НОД(aр,bр)

больше или равна степени НОД(f,g).

a и b (в частности, может делить один из

них, но не оба одновременно), то степень НОД (aр,bр) больше или равна степени НОД(a,b).

число значений р, таких, что степень НОД(ap,bp)

отличается от степени НОД(а,b):

Лемма 2. Пусть с=НОД(а,b). Если число р удовлетворяет условию следствия и если р не делит Resx(a/c,b/c), то НОД(ap,bp)=cp.

это те р, которые делят НОД старших коэффициентов;
это те р, которые делят результант, упоминающийся в лемме (почему у него конечное число делителей !!??).

найти_большое_простое (2М)
если степень_остатка (р,А) или

степень_остатка (р,В)
то С:=модулярный_НОД (А,В,р);
если делит (С,А) и делит (С,В)
то выход С;

простое число, большее чем его аргумент (каждый раз новое

число);

алгоритм степень_остатка проверяет, что редукция по модулю р не меняет степень, т.е. р не делит старший коэффициент;

алгоритм модулярный_НОД применяет алгоритм Евклида по модулю р;

алгоритм делит проверяет, что многочлены делятся над кольцом целых чисел

С:= модулярный_НОД (А,В,р);
E1: если степень (С)=0 то выход 1;

Дано:=р;
Результат:=С;
Цикл пока Дано ≤ 2М
р:=найти_простое (Кроме);
С:= модулярный_НОД (А,В,р);
если степень (С)< степень (Результат) то идти на Е1;
если степень (С)= степень (Результат)
то Результат:=CRT(Результат, Дано, С, р);
Дано:= Дано·р;
если делит (Результат, А) и делит (Результат, В)
то выход Результат;
идти на ЕО;

число, не делящее его аргумент (каждый раз новое число);

CRT

– применяет китайскую теорему об остатках к каждому коэффициенту двух полиномов – Результат (по модулю Дано) и С (по модулю р), представляя целые числа по модулю М между –М/2 и М