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

«Наивный» метод
т.е.
Пример: Вычислить НОД полиномов

Пример:
p5=НОД(f5,g5):
w=х-3, v=х+2, НОД=1,
но w5=v5=х+2 и, таким образом, НОД(w5,v5)=х+2.

Граница для коэффициентов НОД двух полиномов.
Теорема (неравенство Ландау-Миньотта).

Следствие 1.

Лемма 1.
Если число p не делит старший коэффициент НОД(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М)
если степень_остатка (р,А) или степень_остатка (р,В)
то С:=модулярный_НОД (А,В,р);
если делит (С,А) и делит (С,В)
то выход С;

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

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

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