reth::primitives::revm_primitives::alloy_primitives::ruint::algorithms

Function inv_mod

pub fn inv_mod<const BITS: usize, const LIMBS: usize>(
    num: Uint<BITS, LIMBS>,
    modulus: Uint<BITS, LIMBS>,
) -> Option<Uint<BITS, LIMBS>>
Expand description

⚠️ Modular inversion using extended GCD.

It uses the Bezout identity

   a * modulus + b * num = gcd(modulus, num)

where a and b are the cofactors from the extended Euclidean algorithm. A modular inverse only exists if modulus and num are coprime, in which case gcd(modulus, num) is one. Reducing both sides by the modulus then results in the equation b * num = 1 (mod modulus). In other words, the cofactor b is the modular inverse of num.

It differs from gcd_extended in that it only computes the required cofactor, and returns None if the GCD is not one (i.e. when num does not have an inverse).