crypto_bigint/modular/const_monty_form/
inv.rs

1//! Multiplicative inverses of integers in Montgomery form with a constant modulus.
2
3use super::{ConstMontyForm, ConstMontyParams};
4use crate::{
5    modular::SafeGcdInverter, ConstCtOption, Invert, Inverter, Odd, PrecomputeInverter, Uint,
6};
7use core::{fmt, marker::PhantomData};
8use subtle::CtOption;
9
10impl<MOD: ConstMontyParams<SAT_LIMBS>, const SAT_LIMBS: usize, const UNSAT_LIMBS: usize>
11    ConstMontyForm<MOD, SAT_LIMBS>
12where
13    Odd<Uint<SAT_LIMBS>>: PrecomputeInverter<
14        Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>,
15        Output = Uint<SAT_LIMBS>,
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    pub const fn inv(&self) -> ConstCtOption<Self> {
24        let inverter =
25            <Odd<Uint<SAT_LIMBS>> as PrecomputeInverter>::Inverter::new(&MOD::MODULUS, &MOD::R2);
26
27        let maybe_inverse = inverter.inv(&self.montgomery_form);
28        let (inverse, inverse_is_some) = maybe_inverse.components_ref();
29
30        let ret = Self {
31            montgomery_form: *inverse,
32            phantom: PhantomData,
33        };
34
35        ConstCtOption::new(ret, inverse_is_some)
36    }
37
38    /// Computes `self^-1` representing the multiplicative inverse of `self`,
39    /// i.e. `self * self^-1 = 1`.
40    ///
41    /// If the number was invertible, the second element of the tuple is the truthy value,
42    /// otherwise it is the falsy value (in which case the first element's value is unspecified).
43    ///
44    /// This version is variable-time with respect to the value of `self`, but constant-time with
45    /// respect to `MOD`.
46    pub const fn inv_vartime(&self) -> ConstCtOption<Self> {
47        let inverter =
48            <Odd<Uint<SAT_LIMBS>> as PrecomputeInverter>::Inverter::new(&MOD::MODULUS, &MOD::R2);
49
50        let maybe_inverse = inverter.inv_vartime(&self.montgomery_form);
51        let (inverse, inverse_is_some) = maybe_inverse.components_ref();
52
53        let ret = Self {
54            montgomery_form: *inverse,
55            phantom: PhantomData,
56        };
57
58        ConstCtOption::new(ret, inverse_is_some)
59    }
60}
61
62impl<MOD: ConstMontyParams<SAT_LIMBS>, const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Invert
63    for ConstMontyForm<MOD, SAT_LIMBS>
64where
65    Odd<Uint<SAT_LIMBS>>: PrecomputeInverter<
66        Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>,
67        Output = Uint<SAT_LIMBS>,
68    >,
69{
70    type Output = CtOption<Self>;
71
72    fn invert(&self) -> Self::Output {
73        self.inv().into()
74    }
75
76    fn invert_vartime(&self) -> Self::Output {
77        self.inv_vartime().into()
78    }
79}
80
81/// Bernstein-Yang inverter which inverts [`ConstMontyForm`] types.
82pub struct ConstMontyFormInverter<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize>
83where
84    Odd<Uint<LIMBS>>: PrecomputeInverter<Output = Uint<LIMBS>>,
85{
86    inverter: <Odd<Uint<LIMBS>> as PrecomputeInverter>::Inverter,
87    phantom: PhantomData<MOD>,
88}
89
90impl<MOD: ConstMontyParams<SAT_LIMBS>, const SAT_LIMBS: usize, const UNSAT_LIMBS: usize>
91    ConstMontyFormInverter<MOD, SAT_LIMBS>
92where
93    Odd<Uint<SAT_LIMBS>>: PrecomputeInverter<
94        Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>,
95        Output = Uint<SAT_LIMBS>,
96    >,
97{
98    /// Create a new [`ConstMontyFormInverter`] for the given [`ConstMontyParams`].
99    #[allow(clippy::new_without_default)]
100    pub const fn new() -> Self {
101        let inverter = SafeGcdInverter::new(&MOD::MODULUS, &MOD::R2);
102
103        Self {
104            inverter,
105            phantom: PhantomData,
106        }
107    }
108
109    /// Returns either the adjusted modular multiplicative inverse for the argument or None
110    /// depending on invertibility of the argument, i.e. its coprimality with the modulus.
111    pub const fn inv(
112        &self,
113        value: &ConstMontyForm<MOD, SAT_LIMBS>,
114    ) -> ConstCtOption<ConstMontyForm<MOD, SAT_LIMBS>> {
115        let montgomery_form = self.inverter.inv(&value.montgomery_form);
116        let (montgomery_form_ref, is_some) = montgomery_form.components_ref();
117        let ret = ConstMontyForm {
118            montgomery_form: *montgomery_form_ref,
119            phantom: PhantomData,
120        };
121        ConstCtOption::new(ret, is_some)
122    }
123
124    /// Returns either the adjusted modular multiplicative inverse for the argument or None
125    /// depending on invertibility of the argument, i.e. its coprimality with the modulus.
126    ///
127    /// This version is variable-time with respect to the value of `self`, but constant-time with
128    /// respect to `MOD`.
129    pub const fn inv_vartime(
130        &self,
131        value: &ConstMontyForm<MOD, SAT_LIMBS>,
132    ) -> ConstCtOption<ConstMontyForm<MOD, SAT_LIMBS>> {
133        let montgomery_form = self.inverter.inv_vartime(&value.montgomery_form);
134        let (montgomery_form_ref, is_some) = montgomery_form.components_ref();
135        let ret = ConstMontyForm {
136            montgomery_form: *montgomery_form_ref,
137            phantom: PhantomData,
138        };
139        ConstCtOption::new(ret, is_some)
140    }
141}
142
143impl<MOD: ConstMontyParams<SAT_LIMBS>, const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Inverter
144    for ConstMontyFormInverter<MOD, SAT_LIMBS>
145where
146    Odd<Uint<SAT_LIMBS>>: PrecomputeInverter<
147        Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>,
148        Output = Uint<SAT_LIMBS>,
149    >,
150{
151    type Output = ConstMontyForm<MOD, SAT_LIMBS>;
152
153    fn invert(&self, value: &ConstMontyForm<MOD, SAT_LIMBS>) -> CtOption<Self::Output> {
154        self.inv(value).into()
155    }
156
157    fn invert_vartime(&self, value: &ConstMontyForm<MOD, SAT_LIMBS>) -> CtOption<Self::Output> {
158        self.inv_vartime(value).into()
159    }
160}
161
162impl<MOD: ConstMontyParams<SAT_LIMBS>, const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> fmt::Debug
163    for ConstMontyFormInverter<MOD, SAT_LIMBS>
164where
165    Odd<Uint<SAT_LIMBS>>: PrecomputeInverter<
166        Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>,
167        Output = Uint<SAT_LIMBS>,
168    >,
169{
170    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
171        f.debug_struct("ConstMontyFormInverter")
172            .field("modulus", &self.inverter.modulus)
173            .finish()
174    }
175}
176
177#[cfg(test)]
178mod tests {
179    use super::ConstMontyParams;
180    use crate::{const_monty_form, impl_modulus, Inverter, U256};
181
182    impl_modulus!(
183        Modulus,
184        U256,
185        "15477BCCEFE197328255BFA79A1217899016D927EF460F4FF404029D24FA4409"
186    );
187
188    #[test]
189    fn test_self_inverse() {
190        let x =
191            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
192        let x_mod = const_monty_form!(x, Modulus);
193
194        let inv = x_mod.inv().unwrap();
195        let res = x_mod * inv;
196
197        assert_eq!(res.retrieve(), U256::ONE);
198    }
199
200    #[test]
201    fn test_self_inverse_precomputed() {
202        let x =
203            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
204        let x_mod = const_monty_form!(x, Modulus);
205        let inverter = Modulus::precompute_inverter();
206
207        let inv = inverter.invert(&x_mod).unwrap();
208        let res = x_mod * inv;
209
210        assert_eq!(res.retrieve(), U256::ONE);
211    }
212}
crypto_bigint/modular/const_monty_form/inv.rs

crypto_bigint/modular/const_monty_form/
inv.rs
