Next: Jacobi Symbol, Previous: Subquadratic GCD, Up: Greatest Common Divisor Algorithms [Index]
The extended GCD function, or gcdext, calculates gcd(a,b) and also one of the cofactors x and y satisfying a*x+b*y=gcd(a,b). The algorithms used for plain GCD are extended to handle this case.
Lehmer’s algorithm is used for sizes up to GCDEXT_DC_THRESHOLD
. Above
this threshold, GCDEXT is implemented as a loop around HGCD, but with more
book-keeping to keep track of the cofactors.