Function zkp_u256::gcd_extended

pub fn gcd_extended(r0: U256, r1: U256) -> (U256, U256, U256, bool)

Lehmer's extended GCD.

A variation of Euclids algorithm where repeated 64-bit approximations are used to make rapid progress on.

See Jebelean (1994) "A Double-Digit Lehmer-Euclid Algorithm for Finding the GCD of Long Integers".

The function lehmer_double takes two U256's and returns a 64-bit matrix.

The function lehmer_update updates state variables using this matrix. If the matrix makes no progress (because 64 bit precision is not enough) a full precision Euclid step is done, but this happens rarely.

See also mpn_gcdext_lehmer_n in GMP. https://gmplib.org/repo/gmp-6.1/file/tip/mpn/generic/gcdext_lehmer.c#l146