crypto_bigint/modular/
fixed_monty_form.rs

1//! Implements `MontyForm`s, supporting modular arithmetic with a modulus set at runtime.
2
3mod add;
4mod ct;
5pub(super) mod invert;
6mod lincomb;
7mod mod_symbol;
8mod mul;
9mod neg;
10mod pow;
11mod sub;
12
13use super::{
14    FixedMontyParams, Retrieve,
15    const_monty_form::{ConstMontyForm, ConstMontyParams},
16    div_by_2::div_by_2,
17    mul::mul_montgomery_form,
18    reduction::montgomery_retrieve,
19};
20use crate::{MontyForm, Odd, Uint};
21use mul::FixedMontyMultiplier;
22
23/// An integer in Montgomery form represented using `LIMBS` limbs.
24/// The odd modulus is set at runtime.
25#[derive(Debug, Clone, Copy, PartialEq, Eq)]
26pub struct FixedMontyForm<const LIMBS: usize> {
27    montgomery_form: Uint<LIMBS>,
28    params: FixedMontyParams<LIMBS>,
29}
30
31impl<const LIMBS: usize> FixedMontyForm<LIMBS> {
32    /// Instantiates a new `MontyForm` that represents this `integer` mod `MOD`.
33    #[must_use]
34    pub const fn new(integer: &Uint<LIMBS>, params: &FixedMontyParams<LIMBS>) -> Self {
35        let montgomery_form =
36            mul_montgomery_form(integer, &params.r2, &params.modulus, params.mod_neg_inv());
37        Self {
38            montgomery_form,
39            params: *params,
40        }
41    }
42
43    /// Retrieves the integer currently encoded in this `MontyForm`, guaranteed to be reduced.
44    #[must_use]
45    pub const fn retrieve(&self) -> Uint<LIMBS> {
46        montgomery_retrieve(
47            &self.montgomery_form,
48            &self.params.modulus,
49            self.params.mod_neg_inv(),
50        )
51    }
52
53    /// Instantiates a new `MontyForm` that represents zero.
54    #[must_use]
55    pub const fn zero(params: &FixedMontyParams<LIMBS>) -> Self {
56        Self {
57            montgomery_form: Uint::<LIMBS>::ZERO,
58            params: *params,
59        }
60    }
61
62    /// Instantiates a new `MontyForm` that represents 1.
63    #[must_use]
64    pub const fn one(params: &FixedMontyParams<LIMBS>) -> Self {
65        Self {
66            montgomery_form: params.one,
67            params: *params,
68        }
69    }
70
71    /// Returns the parameter struct used to initialize this object.
72    #[must_use]
73    pub const fn params(&self) -> &FixedMontyParams<LIMBS> {
74        &self.params
75    }
76
77    /// Access the `MontyForm` value in Montgomery form.
78    #[must_use]
79    pub const fn as_montgomery(&self) -> &Uint<LIMBS> {
80        &self.montgomery_form
81    }
82
83    /// Mutably access the `MontyForm` value in Montgomery form.
84    pub fn as_montgomery_mut(&mut self) -> &mut Uint<LIMBS> {
85        &mut self.montgomery_form
86    }
87
88    /// Create a `MontyForm` from a value in Montgomery form.
89    #[must_use]
90    pub const fn from_montgomery(integer: Uint<LIMBS>, params: &FixedMontyParams<LIMBS>) -> Self {
91        Self {
92            montgomery_form: integer,
93            params: *params,
94        }
95    }
96
97    /// Extract the value from the `MontyForm` in Montgomery form.
98    #[must_use]
99    pub const fn to_montgomery(&self) -> Uint<LIMBS> {
100        self.montgomery_form
101    }
102
103    /// Performs division by 2, that is returns `x` such that `x + x = self`.
104    #[must_use]
105    pub const fn div_by_2(&self) -> Self {
106        Self {
107            montgomery_form: div_by_2(&self.montgomery_form, &self.params.modulus),
108            params: self.params,
109        }
110    }
111}
112
113impl<const LIMBS: usize> Retrieve for FixedMontyForm<LIMBS> {
114    type Output = Uint<LIMBS>;
115    fn retrieve(&self) -> Self::Output {
116        self.retrieve()
117    }
118}
119
120impl<const LIMBS: usize> MontyForm for FixedMontyForm<LIMBS> {
121    type Integer = Uint<LIMBS>;
122    type Params = FixedMontyParams<LIMBS>;
123    type Multiplier<'a> = FixedMontyMultiplier<'a, LIMBS>;
124
125    fn new_params_vartime(modulus: Odd<Self::Integer>) -> Self::Params {
126        FixedMontyParams::new_vartime(modulus)
127    }
128
129    fn new(value: Self::Integer, params: &Self::Params) -> Self {
130        FixedMontyForm::new(&value, params)
131    }
132
133    fn zero(params: &Self::Params) -> Self {
134        FixedMontyForm::zero(params)
135    }
136
137    fn one(params: &Self::Params) -> Self {
138        FixedMontyForm::one(params)
139    }
140
141    fn params(&self) -> &Self::Params {
142        &self.params
143    }
144
145    fn as_montgomery(&self) -> &Self::Integer {
146        &self.montgomery_form
147    }
148
149    fn into_montgomery(self) -> Self::Integer {
150        self.montgomery_form
151    }
152
153    fn copy_montgomery_from(&mut self, other: &Self) {
154        debug_assert_eq!(self.params, other.params);
155        self.montgomery_form = other.montgomery_form;
156    }
157
158    fn double(&self) -> Self {
159        FixedMontyForm::double(self)
160    }
161
162    fn div_by_2(&self) -> Self {
163        FixedMontyForm::div_by_2(self)
164    }
165
166    fn lincomb_vartime(products: &[(&Self, &Self)]) -> Self {
167        FixedMontyForm::lincomb_vartime(products)
168    }
169}
170
171impl<const LIMBS: usize, P: ConstMontyParams<LIMBS>> From<&ConstMontyForm<P, LIMBS>>
172    for FixedMontyForm<LIMBS>
173{
174    fn from(const_monty_form: &ConstMontyForm<P, LIMBS>) -> Self {
175        Self {
176            montgomery_form: const_monty_form.to_montgomery(),
177            params: P::PARAMS,
178        }
179    }
180}
181
182#[cfg(feature = "zeroize")]
183impl<const LIMBS: usize> zeroize::Zeroize for FixedMontyForm<LIMBS> {
184    fn zeroize(&mut self) {
185        self.montgomery_form.zeroize();
186        self.params.zeroize();
187    }
188}
189
190#[cfg(test)]
191mod tests {
192    use super::FixedMontyParams;
193    use crate::{Limb, Odd, Uint};
194
195    #[test]
196    fn new_params_with_valid_modulus() {
197        let modulus = Odd::new(Uint::from(3u8)).unwrap();
198        let params = FixedMontyParams::<1>::new(modulus);
199
200        assert_eq!(params.mod_leading_zeros, Limb::BITS - 2);
201    }
202}
crypto_bigint/modular/fixed_monty_form.rs

crypto_bigint/modular/
fixed_monty_form.rs
