The Accelerated Euclidean Algorithm

Abstract

We present a new GCD algorithm of two integers or polynomials. The algorithm is iterative and its time complexity is still $$\begin{gathered} O(n \\ lo{g}^{2}nlog \\ logn) \end{gathered}$$ for $n$-bit inputs.