crypto_bigint/modular/monty_form/
inv.rs

1//! Multiplicative inverses of integers in Montgomery form with a modulus set at runtime.
2
3use super::{MontyForm, MontyParams};
4use crate::{
5    modular::SafeGcdInverter, traits::Invert, ConstCtOption, Inverter, Odd, PrecomputeInverter,
6    PrecomputeInverterWithAdjuster, Uint,
7};
8use core::fmt;
9use subtle::CtOption;
10
11impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> MontyForm<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 = self.params.inverter();
25        let maybe_inverse = inverter.inv(&self.montgomery_form);
26        let (inverse, inverse_is_some) = maybe_inverse.components_ref();
27
28        let ret = Self {
29            montgomery_form: *inverse,
30            params: self.params,
31        };
32
33        ConstCtOption::new(ret, 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    pub const fn inv_vartime(&self) -> ConstCtOption<Self> {
45        let inverter = self.params.inverter();
46        let maybe_inverse = inverter.inv_vartime(&self.montgomery_form);
47        let (inverse, inverse_is_some) = maybe_inverse.components_ref();
48
49        let ret = Self {
50            montgomery_form: *inverse,
51            params: self.params,
52        };
53
54        ConstCtOption::new(ret, inverse_is_some)
55    }
56}
57
58impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Invert for MontyForm<SAT_LIMBS>
59where
60    Odd<Uint<SAT_LIMBS>>: PrecomputeInverter<
61        Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>,
62        Output = Uint<SAT_LIMBS>,
63    >,
64{
65    type Output = CtOption<Self>;
66
67    fn invert(&self) -> Self::Output {
68        self.inv().into()
69    }
70
71    fn invert_vartime(&self) -> Self::Output {
72        self.inv_vartime().into()
73    }
74}
75
76impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> MontyParams<SAT_LIMBS>
77where
78    Odd<Uint<SAT_LIMBS>>: PrecomputeInverter<
79        Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>,
80        Output = Uint<SAT_LIMBS>,
81    >,
82{
83    /// Create a modular inverter for the modulus of these params.
84    // TODO(tarcieri): make `pub`?
85    const fn inverter(&self) -> SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS> {
86        SafeGcdInverter::new(&self.modulus, &self.r2)
87    }
88}
89
90impl<const LIMBS: usize> PrecomputeInverter for MontyParams<LIMBS>
91where
92    Odd<Uint<LIMBS>>:
93        PrecomputeInverter<Output = Uint<LIMBS>> + PrecomputeInverterWithAdjuster<Uint<LIMBS>>,
94{
95    type Inverter = MontyFormInverter<LIMBS>;
96    type Output = MontyForm<LIMBS>;
97
98    fn precompute_inverter(&self) -> MontyFormInverter<LIMBS> {
99        MontyFormInverter {
100            inverter: self.modulus.precompute_inverter_with_adjuster(&self.r2),
101            params: *self,
102        }
103    }
104}
105
106/// Bernstein-Yang inverter which inverts [`MontyForm`] types.
107pub struct MontyFormInverter<const LIMBS: usize>
108where
109    Odd<Uint<LIMBS>>: PrecomputeInverter<Output = Uint<LIMBS>>,
110{
111    inverter: <Odd<Uint<LIMBS>> as PrecomputeInverter>::Inverter,
112    params: MontyParams<LIMBS>,
113}
114
115impl<const LIMBS: usize> Inverter for MontyFormInverter<LIMBS>
116where
117    Odd<Uint<LIMBS>>: PrecomputeInverter<Output = Uint<LIMBS>>,
118{
119    type Output = MontyForm<LIMBS>;
120
121    fn invert(&self, value: &MontyForm<LIMBS>) -> CtOption<Self::Output> {
122        debug_assert_eq!(self.params, value.params);
123
124        self.inverter
125            .invert(&value.montgomery_form)
126            .map(|montgomery_form| MontyForm {
127                montgomery_form,
128                params: value.params,
129            })
130    }
131
132    fn invert_vartime(&self, value: &MontyForm<LIMBS>) -> CtOption<Self::Output> {
133        debug_assert_eq!(self.params, value.params);
134
135        self.inverter
136            .invert_vartime(&value.montgomery_form)
137            .map(|montgomery_form| MontyForm {
138                montgomery_form,
139                params: value.params,
140            })
141    }
142}
143
144impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> fmt::Debug for MontyFormInverter<SAT_LIMBS>
145where
146    Odd<Uint<SAT_LIMBS>>: PrecomputeInverter<
147        Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>,
148        Output = Uint<SAT_LIMBS>,
149    >,
150{
151    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
152        f.debug_struct("MontyFormInverter")
153            .field("modulus", &self.inverter.modulus)
154            .finish()
155    }
156}
157
158#[cfg(test)]
159mod tests {
160    use super::{MontyForm, MontyParams};
161    use crate::{Invert, Inverter, Odd, PrecomputeInverter, U256};
162
163    fn params() -> MontyParams<{ U256::LIMBS }> {
164        MontyParams::new_vartime(Odd::<U256>::from_be_hex(
165            "15477BCCEFE197328255BFA79A1217899016D927EF460F4FF404029D24FA4409",
166        ))
167    }
168
169    #[test]
170    fn test_self_inverse() {
171        let params = params();
172        let x =
173            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
174        let x_monty = MontyForm::new(&x, params);
175
176        let inv = x_monty.invert().unwrap();
177        let res = x_monty * inv;
178
179        assert_eq!(res.retrieve(), U256::ONE);
180    }
181
182    #[test]
183    fn test_self_inverse_precomuted() {
184        let params = params();
185        let x =
186            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
187        let x_monty = MontyForm::new(&x, params);
188
189        let inverter = params.precompute_inverter();
190        let inv = inverter.invert(&x_monty).unwrap();
191        let res = x_monty * inv;
192
193        assert_eq!(res.retrieve(), U256::ONE);
194    }
195}
crypto_bigint/modular/monty_form/inv.rs

crypto_bigint/modular/monty_form/
inv.rs
