Эффективное удаление делителей в $k$-арном алгоритме

Один из наиболее эффективных алгоритмов вычисления наибольшего общего делителя при работе с длинными числами – $k$-арный алгоритм. Вычисление наибольшего общего делителя используется во многих криптографических алгоритмах. Если при нахождении наибольшего общего делителя $u$, $v$ в $k$-арном алгоритме бинарные длины чисел $u$ и $v$ близки, то используется шаг редукции $t = |a u + b v|/k$, где ${ 0 < a, \ |b| \leq \lceil \sqrt{k} \rceil{:}\ a u + b v \equiv{} 0 \pmod k}$. Если числа $u$ и $v$ сильно отличаются по длине, то для сокращения $u$ до длины $v$ испольуется операция dmod, которая определяется по формуле $|u-cv|/2^L$, где $c = u v^{-1} \bmod 2^L$, $L = L(u) - L(v)$, а функция $L(a)$ – бинарная длина числа $a$. Ускорение $k$-арного алгоритма проводится путем минимизации количества операций удаления делителей в главном цикле при $k=2^{2W}$, где $W$ – длина машинного слова. Мы объединяем эту процедуру с операцией деления на $2^{iW}$, для которой описана быстрая реализация за $O(1)$ операций, и рассматриваем новый способ вычисления коэффициентов, что в результате позволяет полностью избавиться от удаления делителей перед шагом редукции и позволяет производить удаление делителей перед операцией dmod лишь в $1/3$ случаев, тем самым уменьшив общее количество операций, выполняемых над длинными числами. Предложенный нами метод ускоряет главный цикл $k$-арного алгоритма на $3$–$16\%$ в зависимости от длины числа.