crypto_bigint/modular/const_monty_form/
invert.rs

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

crypto_bigint/modular/const_monty_form/
invert.rs
