Half-GCD

Given integers  and  with close to  bits each, the half-GCD of  and  is a  matrix

with determinant equal to  or 1 such that  and , where  and  each have a number of bits close to .

The half-GCD results by performing roughly half the Euclidean algorithm for computing the greatest common divisor . There is an efficient algorithm for computing the half-GCD of two large numbers which, when applied recursively, allows the greatest common divisor to be computed faster than using the Euclidean algorithm.

REFERENCES:

Aho, A. V.; Hopcroft, J. E.; and Ullmann, J. D. Data Structures and Algorithms. Reading, MA: Addison-Wesley, 1987.

Sedjelmaci, S. M. "The Accelerated Euclidean Algorithm." Poster talk presented at ISAAC 2004, July 4-7, University of Cantabria, Santander, Spain. https://www.risc.uni-linz.ac.at/issac2004/poster-abstracts/abstract27.pdf.