Function num_bigint_dig::algorithms::xgcd

source ·

pub fn xgcd(
    a_in: &BigInt,
    b_in: &BigInt,
    extended: bool
) -> (BigInt, Option<BigInt>, Option<BigInt>)

Expand description

XGCD sets z to the greatest common divisor of a and b and returns z. If extended is true, XGCD returns their value such that z = ax + by.

Allow the inputs a and b to be zero or negative to GCD with the following definitions.

If x or y are not nil, GCD sets their value such that z = ax + by. Regardless of the signs of a and b, z is always >= 0. If a == b == 0, GCD sets z = x = y = 0. If a == 0 and b != 0, GCD sets z = |b|, x = 0, y = sign(b) * 1. If a != 0 and b == 0, GCD sets z = |a|, x = sign(a) * 1, y = 0.