Given integers 
and 
with close to 
bits each, the half-GCD of 
and 
is a 
matrix
![[u v; u^' v^']](/images/equations/Half-GCD/NumberedEquation1.svg) |
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.
