Об ускорении $k$-арного алгоритма вычисления НОД натуральных чисел

В работе исследованы методы ускорения вычисления наибольшего общего делителя натуральных чисел на основе $k$-арного алгоритма, разработанного в 1990 г. Д. Соренсоном. Основная идея $k$-арного алгоритма состоит в вычислении для заданных натуральных чисел $A>B>1$ пары целых чисел $x$ и $y$ таких, что выполнено соотношение $Ax+By\equiv 0 \bmod k$, где параметр $k$ выбирается взаимно простым с $A$ и $B$. Тогда $C=(Ax+By)/k$ примет значение, меньшее $A$, и следующая итерация выполняется с новой парой $(B, C)$. $k$-арный алгоритм обеспечивает значительное уменьшение общего числа итераций по сравнению с классическим алгоритмом Евклида, однако общая производительность $k$-арного алгоритма проигрывает алгоритму Евклида.
Предложено использование заранее вычисленных таблиц параметров алгоритма и показано, что такой подход обеспечивает скорость, при которой $k$-арный алгоритм работает быстрее классического алгоритма Евклида.