//! Constant-time modular inversion via Bernstein-Yang divsteps (SafeGCD).
use super::U256;
use crate::divstep::Divstep;

impl U256 {
    /// Computes the modular multiplicative inverse of `self` modulo `modulus`
    /// in constant time using Bernstein-Yang divsteps (SafeGCD).
    ///
    /// Performs exactly 12 macroiterations of 62 divsteps (744 total), with
    /// no data-dependent branches. Execution time is independent of the input
    /// value, preventing timing side-channel leaks.
    ///
    /// Returns `Some(x)` where `self * x ≡ 1 (mod modulus)`, or `None`
    /// if `gcd(self, modulus) ≠ 1`. Only correct when `modulus` is odd.
    #[inline]
    pub fn mod_inv_ct(&self, modulus: &U256) -> Option<U256> {
        Divstep::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_ct(&P).unwrap(), U256::ONE);
    }

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

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

    /// CT matches VT for multiple values.
    #[test]
    fn matches_vt() {
        let values = [
            U256::ONE,
            U256::from_be_limbs([0, 0, 0, 7]),
            U256::from_be_limbs([0, 0, 0, 42]),
            U256::from_be_limbs([
                0x79BE667EF9DCBBAC, 0x55A06295CE870B07,
                0x029BFCDB2DCE28D9, 0x59F2815B16F81798,
            ]),
            P - U256::ONE,
        ];
        for v in &values {
            assert_eq!(
                v.mod_inv_ct(&P),
                v.mod_inv_vt(&P),
                "CT/VT mismatch for {v:?}"
            );
        }
    }

    /// Modulus multiple has no inverse.
    #[test]
    fn modulus_multiple_no_inverse() {
        assert!(P.mod_inv_ct(&P).is_none());
    }
}
