crypto_bigint/modular/
const_monty_form.rs

1//! Implements `ConstMontyForm`s, supporting modular arithmetic with a constant modulus.
2
3mod add;
4pub(super) mod invert;
5mod lincomb;
6mod mod_symbol;
7mod mul;
8mod neg;
9mod pow;
10mod reduce;
11mod sqrt;
12mod sub;
13
14use super::{
15    FixedMontyParams, PrimeParams, Retrieve, div_by_2::div_by_2, mul::mul_montgomery_form,
16    reduction::montgomery_retrieve,
17};
18use crate::{ConstOne, ConstZero, CtEq, Odd, One, Uint, Zero};
19use core::{fmt::Debug, marker::PhantomData};
20
21#[cfg(feature = "rand_core")]
22use crate::{Random, RandomMod, rand_core::TryRng};
23
24#[cfg(feature = "serde")]
25use {
26    crate::Encoding,
27    serdect::serde::de::Error,
28    serdect::serde::{Deserialize, Deserializer, Serialize, Serializer},
29};
30
31/// Macros to remove the boilerplate code when dealing with constant moduli.
32#[macro_use]
33mod macros;
34mod ct;
35
36/// Trait representing a modulus and its associated constants for converting in and out of
37/// Montgomery form.
38///
39/// To define a type which impls this trait, use the
40/// [`const_monty_params!`][`crate::const_monty_params`] macro.
41pub trait ConstMontyParams<const LIMBS: usize>:
42    Copy + Debug + Default + Eq + Send + Sync + 'static
43{
44    /// Number of limbs required to encode the Montgomery form
45    const LIMBS: usize;
46
47    /// Montgomery parameters constant.
48    const PARAMS: FixedMontyParams<LIMBS>;
49}
50
51/// Trait representing a prime modulus and its associated constants for converting in
52/// and out of Montgomery form.
53///
54/// To define a type which impls this trait, use the
55/// [`const_prime_monty_params!`][`crate::const_prime_monty_params`] macro.
56pub trait ConstPrimeMontyParams<const LIMBS: usize>: ConstMontyParams<LIMBS> {
57    /// Prime parameters constant.
58    const PRIME_PARAMS: PrimeParams<LIMBS>;
59}
60
61/// An integer in Montgomery form modulo `MOD`, represented using `LIMBS` limbs.
62/// The modulus is constant, so it cannot be set at runtime.
63///
64/// Internally, the value is stored in Montgomery form (multiplied by `MOD::PARAMS.one`) until it is retrieved.
65#[derive(Debug, Clone, Copy, PartialEq, Eq)]
66pub struct ConstMontyForm<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> {
67    montgomery_form: Uint<LIMBS>,
68    phantom: PhantomData<MOD>,
69}
70
71#[cfg(feature = "zeroize")]
72impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> zeroize::DefaultIsZeroes
73    for ConstMontyForm<MOD, LIMBS>
74{
75}
76
77impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ConstMontyForm<MOD, LIMBS> {
78    /// The representation of 0 mod `MOD`.
79    pub const ZERO: Self = Self {
80        montgomery_form: Uint::<LIMBS>::ZERO,
81        phantom: PhantomData,
82    };
83
84    /// The representation of 1 mod `MOD`.
85    pub const ONE: Self = Self {
86        montgomery_form: MOD::PARAMS.one,
87        phantom: PhantomData,
88    };
89
90    /// Modulus as an unsigned integer.
91    pub const MODULUS: Odd<Uint<LIMBS>> = *MOD::PARAMS.modulus();
92
93    /// Instantiates a new [`ConstMontyForm`] that represents this `integer` mod `MOD`.
94    #[must_use]
95    pub const fn new(integer: &Uint<LIMBS>) -> Self {
96        let montgomery_form = mul_montgomery_form(
97            integer,
98            &MOD::PARAMS.r2,
99            &MOD::PARAMS.modulus,
100            MOD::PARAMS.mod_neg_inv(),
101        );
102
103        Self {
104            montgomery_form,
105            phantom: PhantomData,
106        }
107    }
108
109    /// Retrieves the integer currently encoded in this [`ConstMontyForm`], guaranteed to be reduced.
110    #[must_use]
111    pub const fn retrieve(&self) -> Uint<LIMBS> {
112        montgomery_retrieve(
113            &self.montgomery_form,
114            &MOD::PARAMS.modulus,
115            MOD::PARAMS.mod_neg_inv(),
116        )
117    }
118
119    /// Access the `ConstMontyForm` value in Montgomery form.
120    #[must_use]
121    pub const fn as_montgomery(&self) -> &Uint<LIMBS> {
122        &self.montgomery_form
123    }
124
125    /// Mutably access the `ConstMontyForm` value in Montgomery form.
126    pub fn as_montgomery_mut(&mut self) -> &mut Uint<LIMBS> {
127        &mut self.montgomery_form
128    }
129
130    /// Create a `ConstMontyForm` from a value in Montgomery form.
131    #[must_use]
132    pub const fn from_montgomery(integer: Uint<LIMBS>) -> Self {
133        Self {
134            montgomery_form: integer,
135            phantom: PhantomData,
136        }
137    }
138
139    /// Extract the value from the `ConstMontyForm` in Montgomery form.
140    #[must_use]
141    pub const fn to_montgomery(&self) -> Uint<LIMBS> {
142        self.montgomery_form
143    }
144
145    /// Performs division by 2, that is returns `x` such that `x + x = self`.
146    #[must_use]
147    pub const fn div_by_2(&self) -> Self {
148        Self {
149            montgomery_form: div_by_2(&self.montgomery_form, &MOD::PARAMS.modulus),
150            phantom: PhantomData,
151        }
152    }
153}
154
155impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> Default for ConstMontyForm<MOD, LIMBS> {
156    fn default() -> Self {
157        Self::ZERO
158    }
159}
160
161impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ConstZero for ConstMontyForm<MOD, LIMBS> {
162    const ZERO: Self = Self::ZERO;
163}
164
165impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> Zero for ConstMontyForm<MOD, LIMBS> {
166    #[inline(always)]
167    fn zero() -> Self {
168        Self::ZERO
169    }
170}
171
172impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> num_traits::Zero
173    for ConstMontyForm<MOD, LIMBS>
174{
175    fn zero() -> Self {
176        Self::ZERO
177    }
178
179    fn is_zero(&self) -> bool {
180        self.ct_eq(&Self::ZERO).into()
181    }
182}
183
184impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ConstOne for ConstMontyForm<MOD, LIMBS> {
185    const ONE: Self = Self::ONE;
186}
187
188impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> One for ConstMontyForm<MOD, LIMBS> {
189    #[inline(always)]
190    fn one() -> Self {
191        Self::ONE
192    }
193}
194
195impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> num_traits::One
196    for ConstMontyForm<MOD, LIMBS>
197{
198    fn one() -> Self {
199        Self::ONE
200    }
201
202    fn is_one(&self) -> bool {
203        self.ct_eq(&Self::ONE).into()
204    }
205}
206
207#[cfg(feature = "rand_core")]
208impl<MOD, const LIMBS: usize> Random for ConstMontyForm<MOD, LIMBS>
209where
210    MOD: ConstMontyParams<LIMBS>,
211{
212    #[inline]
213    fn try_random_from_rng<R: TryRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
214        Ok(Self::new(&Uint::try_random_mod_vartime(
215            rng,
216            MOD::PARAMS.modulus.as_nz_ref(),
217        )?))
218    }
219}
220
221impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> Retrieve for ConstMontyForm<MOD, LIMBS> {
222    type Output = Uint<LIMBS>;
223    fn retrieve(&self) -> Self::Output {
224        self.retrieve()
225    }
226}
227
228#[cfg(feature = "serde")]
229impl<'de, MOD, const LIMBS: usize> Deserialize<'de> for ConstMontyForm<MOD, LIMBS>
230where
231    MOD: ConstMontyParams<LIMBS>,
232    Uint<LIMBS>: Encoding,
233{
234    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
235    where
236        D: Deserializer<'de>,
237    {
238        Uint::<LIMBS>::deserialize(deserializer).and_then(|montgomery_form| {
239            if montgomery_form < MOD::PARAMS.modulus.0 {
240                Ok(Self {
241                    montgomery_form,
242                    phantom: PhantomData,
243                })
244            } else {
245                Err(D::Error::custom("montgomery form must be reduced"))
246            }
247        })
248    }
249}
250
251#[cfg(feature = "serde")]
252impl<MOD, const LIMBS: usize> Serialize for ConstMontyForm<MOD, LIMBS>
253where
254    MOD: ConstMontyParams<LIMBS>,
255    Uint<LIMBS>: Encoding,
256{
257    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
258    where
259        S: Serializer,
260    {
261        self.montgomery_form.serialize(serializer)
262    }
263}
crypto_bigint/modular/const_monty_form.rs

crypto_bigint/modular/
const_monty_form.rs
