Novel approach to shortening convergence of Euclidean’s greatest common divisor algorithm

Euclidean greatest common divisor (GCD) algorithm is a common and extraordinarily simple algorithm used to determine the highest common factor (HCF) of two numbers. Its ubiquitous application leverages its very high usefulness. It constitutes the basis for Rivest, Shamir, and Adleman (RSA) and data encryption standard (DES) algorithms, which are commonly used for security on the Internet. Many versions of the algorithm have been developed for various purposes. These include binary GCD, extended GCD, and GCD for polynomials, to mention a few. However, the algorithm delays convergence, particularly the classical Euclidean algorithm, and the pattern of computing it has mostly been successive division to get the quotient and remainder. All these versions either did not adequately address the convergence delay problem or inconsistently worsened it. In our study, we employ a different approach, expanding the divisor to match multiple of the remainder. This method not only computes the GCD accurately but also reduces the convergence delay by about half of the original convergence point of the classical algorithm. We prove that the technique often introduces a common difference among groups of succeeding dividends. Also, an accompanying common quotient has been proven, in this work, to be a universal constant 2. The usefulness of this method is that the Bezout pair promises to be computable in shorter steps because of fewer quotients computed (with possible improved performance) than the other versions, which in turn can speed up the RSA computation.