crypto_bigint/uint/modular/constant_mod/
const_inv.rs

1use core::marker::PhantomData;
2
3use subtle::CtOption;
4
5use crate::{modular::inv::inv_montgomery_form, traits::Invert, CtChoice, NonZero};
6
7use super::{Residue, ResidueParams};
8
9impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> {
10    /// Computes the residue `self^-1` representing the multiplicative inverse of `self`.
11    /// I.e. `self * self^-1 = 1`.
12    /// If the number was invertible, the second element of the tuple is the truthy value,
13    /// otherwise it is the falsy value (in which case the first element's value is unspecified).
14    pub const fn invert(&self) -> (Self, CtChoice) {
15        let (montgomery_form, is_some) = inv_montgomery_form(
16            &self.montgomery_form,
17            &MOD::MODULUS,
18            &MOD::R3,
19            MOD::MOD_NEG_INV,
20        );
21
22        let value = Self {
23            montgomery_form,
24            phantom: PhantomData,
25        };
26
27        (value, is_some)
28    }
29}
30
31impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Invert for Residue<MOD, LIMBS> {
32    type Output = CtOption<Self>;
33    fn invert(&self) -> Self::Output {
34        let (value, is_some) = self.invert();
35        CtOption::new(value, is_some.into())
36    }
37}
38
39impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Invert for NonZero<Residue<MOD, LIMBS>> {
40    type Output = Self;
41    fn invert(&self) -> Self::Output {
42        // Always succeeds for a non-zero argument
43        let (value, _is_some) = self.as_ref().invert();
44        NonZero::new(value).unwrap()
45    }
46}
47
48#[cfg(test)]
49mod tests {
50    use crate::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256};
51
52    impl_modulus!(
53        Modulus,
54        U256,
55        "15477BCCEFE197328255BFA79A1217899016D927EF460F4FF404029D24FA4409"
56    );
57
58    #[test]
59    fn test_self_inverse() {
60        let x =
61            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
62        let x_mod = const_residue!(x, Modulus);
63
64        let (inv, _is_some) = x_mod.invert();
65        let res = x_mod * inv;
66
67        assert_eq!(res.retrieve(), U256::ONE);
68    }
69}
crypto_bigint/uint/modular/constant_mod/const_inv.rs

crypto_bigint/uint/modular/constant_mod/
const_inv.rs
