Function ruint::algorithms::gcd_extended

source · 
pub fn gcd_extended<const BITS: usize, const LIMBS: usize>(
    a: Uint<BITS, LIMBS>,
    b: Uint<BITS, LIMBS>
) -> (Uint<BITS, LIMBS>, Uint<BITS, LIMBS>, Uint<BITS, LIMBS>, bool)
Expand description

⚠️ Lehmer’s extended GCD.

Warning. This struct is not part of the stable API.

Returns (gcd, x, y, sign) such that gcd = a * x + b * y.

§Algorithm

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