3.2.2. Алгоритм Евклида для полиномов над полем

Пусть теперь J — пале, и пусть — два полинома в Как мы уже видели, повторным применением алгоритма деления PDF, описанного в разд. 3.1.1, можно легко вычислить наибольший общий делитель полиномов

Если — наибольший общий делитель полиномов то ясно, что — делитель каждого полинома из множества

где — произвольные полиномы из . Возникает вопрос, принадлежит ли этому множеству сам , т.е. можно ли найти два полинома такие, что

Имеет место следующая

Теорема 3.2.4. Пусть J — поле, и рассмотрим полиномы Если то в существуют два полинома такие, что

Доказательство. Из всех полиномов вида (F), не равных тождественно нулю, выберем полином наименьшей степени и обозначим его Если не делит то по теореме 3.1.1 мы имеем Но тогда полином имеет вид (F), в противоречие с выбором

Следствие 3.2.5. Необходимым и достаточным условием, чтобы два полинома из поле, были взаимно просты, является существование двух полиномов таких, что

Полиномы в теореме 3.2.4 не единственны. Действительно, если удовлетворяют требованиям теоремы, то им удовлетворяют и полиномы

где — произвольный полином из (Проверьте это непосредственной подстановкой.) Поэтому можно выбрать произвольно высокой степени. Однако для их степеней имеются ограничения снизу.

Теорема 3.2.6. Пусть J — поле, и рассмотрим полиномы из . Если , то в существуют два единственных полинома степени которых меньше степеней полиномов соответственно, такие, что

Доказательство. Для конструктивного доказательства см. ниже расширенный алгоритм Евклида.

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

ХЕА-Р.

Расширенный алгоритм Евклида для полиномов над полем (Extended Euclidean Algorithm Polynomials over a Field)

Вход: - поле.

Выход: такие, что

1. [Инициализация]

2. [Основной цикл] Пока выполнять

3. [Выход] Вернуть

Анализ времени работы алгоритма ХЕА-Р. Ясно, что время работы этого алгоритма доминируется временем выполнения шага 2.

Поскольку мы работаем в поле, первое выполнение алгоритма PDF требует времени , где кроме того, первое выполнение каждого из полиномиальных умножений также происходит за время и оно явно доминирует время выполнения каждого из соответствующих полиномиальных вычитаний. Поэтому время первого выполнения шага 2 равно что доминирует и время всех его последующих выполнений (проверьте это).

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

Пример. Рассмотрим поле и полиномы над этим полем. Применяя ХЕА-Р к получаем следующую таблицу (работая с множеством неотрицательных целых чисел):

Проверка:

Эти вычисления показывают, что — наибольший общий делитель двух исходных полиномов. Как мы уже отмечали, каждый отличный от нуля элемент поля обратим, следовательно, любое ненулевое кратное наибольшего общего делителя — также наибольший общий делитель. Поэтому удобно разделить результат на его старший коэффициент и именно полученный нормированный полином назвать наибольшим общим делителем двух данных полиномов. Соответственно таким наибольшим общим делителем В приведенном выше примере будет 1, а не .

Если — неприводимый полином в — простое число, то мы можем воспользоваться приведенным выше алгоритмом так же, как при работе с целыми числами, чтобы вычислить обратный к полиному , где . Мы просто применяем ХЕА-Р к и получаем полиномы такие, что

Тогда, вычисляя значение последнего выражения в точке а, где мы получаем откуда следует, что обратим в

Рассмотрим теперь другой пример, и сконцентрируем наше внимание на росте коэффициентов членов последовательности полиномиальных остатков.

Пример. Рассмотрим полиномы Применяя алгоритм Евклида над рациональными числами, получаем такие последовательности:

Как и прежде,

Рост коэффициентов последовательности полиномиальных остатков мажет быть минимизирован, если каждый член, как только

он получен, нормируется. В этом случае мы получаем

Лействительно, мы видим, что цель достигнута, но ценой вычислений целых чисел на каждом шаге, чтобы максимально редуцировать дроби.

Из этого примера видно, что использовать арифметику рациональных чисел для вычисления последовательности полиномиальных остатков нецелесообразно; с одной стороны, число требуемых для максимального редуцирования коэффициентов вычислений целых чисел слишком велико и, с другой стороны, отказ от редукции ведет в стремительному росту выражения.