//! Variable-time modular inversion via Lehmer's extended GCD algorithm.
use super::U256;
use crate::gcd_state::GcdState;

impl U256 {
    /// Computes the modular multiplicative inverse of `self` modulo `modulus`
    /// using Lehmer's extended GCD algorithm (variable time).
    ///
    /// The Lehmer algorithm is deeply branchy with variable iteration count,
    /// leaking the input through timing. For cryptographic contexts where
    /// this matters, use `mod_inv_ct` (enabled via the `ct` feature flag).
    ///
    /// Returns `Some(x)` where `self * x ≡ 1 (mod modulus)`, or `None`
    /// if `gcd(self, modulus) ≠ 1`.
    #[inline]
    pub fn mod_inv_vt(&self, modulus: &U256) -> Option<U256> {
        GcdState::new(*modulus, *self).run().inverse()
    }
}

#[cfg(test)]
mod ai_tests {
    use super::*;
    const P: U256 = U256::from_be_limbs([
        0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
        0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
    ]);

    /// Inverse of 1 is 1.
    #[test]
    fn inverse_of_one() {
        assert_eq!(U256::ONE.mod_inv_vt(&P).unwrap(), U256::ONE);
    }

    /// Roundtrip: a * inv(a) = 1.
    #[test]
    fn roundtrip() {
        let gx = U256::from_be_limbs([
            0x79BE667EF9DCBBAC, 0x55A06295CE870B07,
            0x029BFCDB2DCE28D9, 0x59F2815B16F81798,
        ]);
        let inv = gx.mod_inv_vt(&P).unwrap();
        assert_eq!(gx.mul_mod(&inv, &P), U256::ONE);
    }

    /// Zero has no inverse.
    #[test]
    fn zero_has_no_inverse() {
        assert!(U256::ZERO.mod_inv_vt(&P).is_none());
    }
}
