О расширенном алгоритме Джебелеана--Вебера--Седжелмаси вычисления наибольшего общего делителя

Abstract

Существует большое количество различных алгоритмов вычисления Н.О.Д. Прежде всего стоит отметить алгоритмы типа Шонхаге. Они используются для очень больших чисел и имеют наилучшую асимптотическую сложность в худшем случае --- $O(n\log^2(n)\log(\log(n)))$.
Для чисел поменьше используются обобщенный бинарные алгоритмы. Все они основаны на $k$-арной редукции: $\alpha \gcd(u,v)=\gcd(v,\frac{|au \pm bv|}{k})$, целые $u>v>0$, $\gcd(u,k)=\gcd(v,k)=1$, $\alpha \geqslant 1$. Знак $+$ или $-$ ставится в зависимости от версии выбранного алгоритма. Основная задача --- подобрать коэффициенты $a,b$ таким образом, чтобы выполнялось $au+bv=0\bmod k$. Число $k$ обычно выбирают равным простому числу или степени простого числа. Недостаток алгоритмов в том, что в ходе вычислений могут накапливаться дополнительные множители, поэтому в рекуррентном соотношении в начале стоит множитель $\alpha \geqslant 1$. Если $k=2^s$, то получаем обобщенные бинарные алгоритмы. Вебер первым предложил алгоритм поиска коэффициентов на основе подаваемых чисел, его обобщенный бинарный алгоритм работает в пять раз быстрее, чем бинарный алгоритм. Седжелмаси модифицировал алгоритм Джебелеана-Вебера, избавив его от дополнительных множителей, асимптотическая сложность алгоритма в худшем случае --- $O(n^2/\log(n))$.

Коэффициенты Безу --- представление Н.О.Д. $d$ чисел $A,B$ в виде линейной комбинации $Ax + By = d$, где $x$ и $y$
--- целые числа, называемые коэффициентами Безу. В этой статье предложен расширенный алгоритм Джебелеана--Вебера--Седжелмаси вычисления Н.О.Д двух натуральных чисел, выводятся необходимые формулы и приводятся примеры, показывающие как можно вычислять обратные элементы.