Вычисление коэффициентов Безу для $k$-арного алгоритма нахождения НОД

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