crypto_bigint/modular/fixed_monty_form/
invert.rs

1//! Multiplicative inverses of integers in Montgomery form with a modulus set at runtime.
2
3use super::{FixedMontyForm, FixedMontyParams};
4use crate::{CtOption, modular::SafeGcdInverter, traits::Invert};
5
6impl<const LIMBS: usize> FixedMontyForm<LIMBS> {
7    /// Computes `self^-1` representing the multiplicative inverse of `self`.
8    /// i.e. `self * self^-1 = 1`.
9    ///
10    /// If the number was invertible, the second element of the tuple is the truthy value,
11    /// otherwise it is the falsy value (in which case the first element's value is unspecified).
12    #[deprecated(since = "0.7.0", note = "please use `invert` instead")]
13    #[must_use]
14    pub const fn inv(&self) -> CtOption<Self> {
15        self.invert()
16    }
17
18    /// Computes `self^-1` representing the multiplicative inverse of `self`.
19    /// i.e. `self * self^-1 = 1`.
20    ///
21    /// If the number was invertible, the second element of the tuple is the truthy value,
22    /// otherwise it is the falsy value (in which case the first element's value is unspecified).
23    #[must_use]
24    pub const fn invert(&self) -> CtOption<Self> {
25        let inverter = self.params.inverter();
26        let maybe_inverse = inverter.invert(&self.montgomery_form);
27
28        let ret = Self {
29            montgomery_form: maybe_inverse.to_inner_unchecked(),
30            params: self.params,
31        };
32
33        CtOption::new(ret, maybe_inverse.is_some())
34    }
35
36    /// Computes `self^-1` representing the multiplicative inverse of `self`.
37    /// i.e. `self * self^-1 = 1`.
38    ///
39    /// If the number was invertible, the second element of the tuple is the truthy value,
40    /// otherwise it is the falsy value (in which case the first element's value is unspecified).
41    ///
42    /// This version is variable-time with respect to the value of `self`, but constant-time with
43    /// respect to `self`'s `params`.
44    #[deprecated(since = "0.7.0", note = "please use `invert_vartime` instead")]
45    #[must_use]
46    pub const fn inv_vartime(&self) -> CtOption<Self> {
47        self.invert_vartime()
48    }
49
50    /// Computes `self^-1` representing the multiplicative inverse of `self`.
51    /// i.e. `self * self^-1 = 1`.
52    ///
53    /// If the number was invertible, the second element of the tuple is the truthy value,
54    /// otherwise it is the falsy value (in which case the first element's value is unspecified).
55    ///
56    /// This version is variable-time with respect to the value of `self`, but constant-time with
57    /// respect to `self`'s `params`.
58    #[must_use]
59    pub const fn invert_vartime(&self) -> CtOption<Self> {
60        let inverter = self.params.inverter();
61        let maybe_inverse = inverter.invert_vartime(&self.montgomery_form);
62
63        let ret = Self {
64            montgomery_form: maybe_inverse.to_inner_unchecked(),
65            params: self.params,
66        };
67
68        CtOption::new(ret, maybe_inverse.is_some())
69    }
70}
71
72impl<const LIMBS: usize> Invert for FixedMontyForm<LIMBS> {
73    type Output = CtOption<Self>;
74
75    fn invert(&self) -> Self::Output {
76        self.invert()
77    }
78
79    fn invert_vartime(&self) -> Self::Output {
80        self.invert_vartime()
81    }
82}
83
84impl<const LIMBS: usize> FixedMontyParams<LIMBS> {
85    /// Create a modular inverter for the modulus of these params.
86    const fn inverter(&self) -> SafeGcdInverter<LIMBS> {
87        SafeGcdInverter::new_with_inverse(&self.modulus, self.mod_inv, &self.r2)
88    }
89}
90
91#[cfg(test)]
92mod tests {
93    use super::{FixedMontyForm, FixedMontyParams};
94    use crate::{Odd, U256};
95
96    fn params() -> FixedMontyParams<{ U256::LIMBS }> {
97        FixedMontyParams::new_vartime(Odd::<U256>::from_be_hex(
98            "15477BCCEFE197328255BFA79A1217899016D927EF460F4FF404029D24FA4409",
99        ))
100    }
101
102    #[test]
103    fn test_self_inverse() {
104        let params = params();
105        let x =
106            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
107        let x_monty = FixedMontyForm::new(&x, &params);
108
109        let inv = x_monty.invert().unwrap();
110        let res = x_monty * inv;
111
112        assert_eq!(res.retrieve(), U256::ONE);
113    }
114}
crypto_bigint/modular/fixed_monty_form/invert.rs

crypto_bigint/modular/fixed_monty_form/
invert.rs
