//! Fermat-based modular inversion test oracle.
use super::U256;

impl U256 {
    /// Computes the modular inverse of `self` modulo `modulus` using Fermat's
    /// little theorem: `a^(p-2) mod p` for prime `p`.
    ///
    /// Returns `Some(inverse)` when `self` is non-zero mod `modulus`, or `None`
    /// when `self` is zero or a multiple of `modulus`. This is a test oracle —
    /// trivially correct but slow (~7µs) — used exclusively to validate the
    /// SafeGCD implementation. Not wired into any dispatcher.
    ///
    /// Only correct when `modulus` is prime. For composite moduli the result
    /// is meaningless.
    #[allow(dead_code)]
    pub(crate) fn mod_inv_fermat(&self, modulus: &U256) -> Option<U256> {
        let reduced = self.modulo(modulus);
        if reduced.is_zero() {
            return None;
        }

        let (exp, _) = modulus.overflowing_sub(&U256::from_be_limbs([0, 0, 0, 2]));
        Some(reduced.pow_mod(&exp, modulus))
    }
}

#[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_fermat(&P).unwrap(), U256::ONE);
    }

    /// Inverse of 2 mod P is (P + 1) / 2.
    #[test]
    fn inverse_of_two() {
        let two = U256::from_be_limbs([0, 0, 0, 2]);
        let inv = two.mod_inv_fermat(&P).unwrap();
        assert_eq!(two.mul_mod(&inv, &P), U256::ONE);
    }

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

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

    /// Matches Lehmer mod_inv for the generator x-coordinate.
    #[test]
    fn matches_lehmer() {
        let gx = U256::from_be_limbs([
            0x79BE667EF9DCBBAC, 0x55A06295CE870B07,
            0x029BFCDB2DCE28D9, 0x59F2815B16F81798,
        ]);
        let fermat = gx.mod_inv_fermat(&P).unwrap();
        let lehmer = gx.mod_inv(&P).unwrap();
        assert_eq!(fermat, lehmer);
    }

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

    /// Inverse of P-1 is P-1.
    #[test]
    fn inverse_of_p_minus_one() {
        let p_minus_1 = P - U256::ONE;
        let inv = p_minus_1.mod_inv_fermat(&P).unwrap();
        assert_eq!(inv, p_minus_1);
    }
}
