//! Modular multiplicative inverse of a [`U256`] value.
//!
//! Dispatches to `mod_inv_ct` (constant-time, Bernstein-Yang divsteps) when
//! the `ct-inv` feature is enabled, or `mod_inv_vt` (variable-time, Lehmer GCD)
//! by default.
use super::U256;

impl U256 {
    /// Computes the modular multiplicative inverse of `self` modulo `modulus`.
    ///
    /// Returns `Some(x)` where `self * x ≡ 1 (mod modulus)`, or `None`
    /// if `gcd(self, modulus) ≠ 1` (i.e. the inverse does not exist).
    ///
    /// With the `ct-inv` feature enabled, this uses Bernstein-Yang divsteps
    /// (SafeGCD) for constant-time execution. Without the feature, this
    /// uses Lehmer's extended GCD (variable-time but faster).
    ///
    /// # Examples
    ///
    /// ```
    /// use cnfy_uint::u256::U256;
    /// let P = U256::from_be_limbs([
    ///     0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
    ///     0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
    /// ]);
    ///
    /// let a = U256::from_be_limbs([0, 0, 0, 7]);
    /// let inv = a.mod_inv(&P).unwrap();
    /// assert_eq!(a.mul_mod(&inv, &P), U256::from_be_limbs([0, 0, 0, 1]));
    /// ```
    #[inline]
    pub fn mod_inv(&self, modulus: &U256) -> Option<U256> {
        #[cfg(feature = "ct-inv")]
        { self.mod_inv_ct(modulus) }
        #[cfg(not(feature = "ct-inv"))]
        { self.mod_inv_vt(modulus) }
    }
}

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

    /// Dispatcher produces the same result as the VT variant.
    #[test]
    fn matches_vt() {
        let values = [
            U256::ONE,
            U256::from_be_limbs([0, 0, 0, 7]),
            U256::from_be_limbs([
                0x79BE667EF9DCBBAC, 0x55A06295CE870B07,
                0x029BFCDB2DCE28D9, 0x59F2815B16F81798,
            ]),
        ];
        for v in &values {
            assert_eq!(v.mod_inv(&P), v.mod_inv_vt(&P));
        }
    }
}

#[cfg(test)]
mod human_tests {

    use super::*;
    const P: U256 = U256::from_be_limbs([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F]);

    /// Random 256-bit value, inverse verified against reference implementation.
    #[test]
    fn random_inverse_a() {
        let a = U256::from_be_bytes([
            43, 159, 22, 142, 78, 236, 241, 198, 156, 188, 193, 220, 161, 20, 133, 160, 112, 18,
            246, 193, 7, 26, 35, 155, 159, 215, 237, 219, 146, 47, 131, 134,
        ]);
        let inv = a.mod_inv(&P).unwrap();
        assert_eq!(
            inv,
            U256::from_be_bytes([
                40, 198, 37, 158, 246, 171, 182, 142, 135, 78, 160, 116, 84, 251, 173, 123, 239,
                170, 145, 192, 22, 157, 124, 219, 237, 145, 206, 170, 214, 239, 144, 34,
            ]),
        );
    }

    #[test]
    fn b() {
        assert_eq!(
            U256::MAX.mod_inv(&P).unwrap(),
            U256([
                804538104391034776,
                8973775910322158119,
                2827781017362681704,
                13709826823187651245,
            ])
        );
    }
}
