crypto_bigint/
modular.rs

1//! Modular arithmetic support.
2//!
3//! This module provides support for various modular arithmetic operations, implemented in terms of
4//! Montgomery form.
5//!
6//! # Constant moduli
7//!
8//! The [`ConstMontyForm`] and [`ConstMontyParams`] types implement support for modular arithmetic
9//! where the modulus is fixed at compile-time.
10//!
11//! The [`const_monty_params!`][`crate::const_monty_params`] macro can be used to define Montgomery
12//! parameters at compile-time from a modulus, whereas the [`const_monty_form!`][`crate::const_monty_form`]
13//! macro can define a [`ConstMontyForm`] constant.
14//!
15//! # Dynamic moduli chosen at runtime
16//!
17//! The [`FixedMontyForm`] and [`FixedMontyParams`] types implement support for modular arithmetic where
18//! the modulus can vary at runtime.
19
20mod const_monty_form;
21mod fixed_monty_form;
22mod lincomb;
23mod reduction;
24
25mod add;
26pub(crate) mod bingcd;
27mod div_by_2;
28mod monty_params;
29mod mul;
30mod pow;
31mod prime_params;
32pub(crate) mod safegcd;
33mod sqrt;
34mod sub;
35
36#[cfg(feature = "alloc")]
37pub(crate) mod boxed_monty_form;
38
39pub use self::{
40    const_monty_form::{ConstMontyForm, ConstMontyParams, ConstPrimeMontyParams},
41    fixed_monty_form::FixedMontyForm,
42    monty_params::{FixedMontyParams, MontyParams},
43    prime_params::PrimeParams,
44};
45
46pub(crate) use self::safegcd::SafeGcdInverter;
47
48#[cfg(feature = "alloc")]
49pub use self::{boxed_monty_form::BoxedMontyForm, monty_params::boxed::BoxedMontyParams};
50
51/// A generalization for numbers kept in optimized representations (e.g. Montgomery)
52/// that can be converted back to the original form.
53pub trait Retrieve {
54    /// The original type.
55    type Output;
56
57    /// Convert the number back from the optimized representation.
58    fn retrieve(&self) -> Self::Output;
59}
60
61#[cfg(test)]
62mod tests {
63    use crate::{
64        NonZero, U64, U128, U256, Uint, const_monty_params,
65        modular::{
66            const_monty_form::{ConstMontyForm, ConstMontyParams},
67            mul::{mul_montgomery_form, square_montgomery_form},
68            reduction::montgomery_reduction,
69        },
70    };
71
72    const_monty_params!(
73        Modulus1,
74        U256,
75        "73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001"
76    );
77
78    #[test]
79    fn test_montgomery_params() {
80        assert_eq!(
81            Modulus1::PARAMS.one,
82            U256::from_be_hex("1824b159acc5056f998c4fefecbc4ff55884b7fa0003480200000001fffffffe")
83        );
84        assert_eq!(
85            Modulus1::PARAMS.r2,
86            U256::from_be_hex("0748d9d99f59ff1105d314967254398f2b6cedcb87925c23c999e990f3f29c6d")
87        );
88        assert_eq!(
89            Modulus1::PARAMS.mod_neg_inv(),
90            U64::from_be_hex("fffffffeffffffff").limbs[0]
91        );
92    }
93
94    const_monty_params!(Modulus128, U128, "000000087b57be17f0ecdbf18a227bd9");
95
96    const_monty_params!(
97        Modulus256,
98        U256,
99        "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"
100    );
101
102    #[test]
103    fn test_reducing_one() {
104        // Divide the value R by R, which should equal 1
105        assert_eq!(
106            montgomery_reduction::<{ Modulus256::LIMBS }>(
107                &(Modulus256::PARAMS.one, Uint::ZERO),
108                &Modulus256::PARAMS.modulus,
109                Modulus256::PARAMS.mod_neg_inv()
110            ),
111            Uint::ONE
112        );
113    }
114
115    #[test]
116    fn test_reducing_r2() {
117        // Divide the value R^2 by R, which should equal R
118        assert_eq!(
119            montgomery_reduction::<{ Modulus256::LIMBS }>(
120                &(Modulus256::PARAMS.r2, Uint::ZERO),
121                &Modulus256::PARAMS.modulus,
122                Modulus256::PARAMS.mod_neg_inv()
123            ),
124            Modulus256::PARAMS.one
125        );
126    }
127
128    #[test]
129    fn test_reducing_r2_wide() {
130        // Divide the value ONE^2 by R, which should equal ONE
131        let (lo, hi) = Modulus256::PARAMS.one.widening_square();
132        assert_eq!(
133            montgomery_reduction::<{ Modulus256::LIMBS }>(
134                &(lo, hi),
135                &Modulus256::PARAMS.modulus,
136                Modulus256::PARAMS.mod_neg_inv()
137            ),
138            Modulus256::PARAMS.one
139        );
140    }
141
142    #[test]
143    fn test_reducing_xr_wide() {
144        // Reducing xR should return x
145        let x =
146            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
147        let product = x.widening_mul(&Modulus256::PARAMS.one);
148        assert_eq!(
149            montgomery_reduction::<{ Modulus256::LIMBS }>(
150                &product,
151                &Modulus256::PARAMS.modulus,
152                Modulus256::PARAMS.mod_neg_inv()
153            ),
154            x
155        );
156    }
157
158    #[test]
159    fn test_reducing_xr2_wide() {
160        // Reducing xR^2 should return xR
161        let x =
162            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
163        let product = x.widening_mul(&Modulus256::PARAMS.r2);
164
165        // Computing xR mod modulus without Montgomery reduction
166        let (lo, hi) = x.widening_mul(&Modulus256::PARAMS.one);
167        let c = lo.concat(&hi);
168        let red =
169            c.rem_vartime(&NonZero::new(Modulus256::PARAMS.modulus.0.concat(&U256::ZERO)).unwrap());
170        let (lo, hi) = red.split();
171        assert_eq!(hi, Uint::ZERO);
172
173        assert_eq!(
174            montgomery_reduction::<{ Modulus256::LIMBS }>(
175                &product,
176                &Modulus256::PARAMS.modulus,
177                Modulus256::PARAMS.mod_neg_inv()
178            ),
179            lo
180        );
181    }
182
183    #[test]
184    fn monty_mul_one_r() {
185        // Multiply 1 by R and divide by R, which should equal 1
186        assert_eq!(
187            mul_montgomery_form::<{ Modulus128::LIMBS }>(
188                &Uint::ONE,
189                &Modulus128::PARAMS.one,
190                &Modulus128::PARAMS.modulus,
191                Modulus128::PARAMS.mod_neg_inv()
192            ),
193            Uint::ONE
194        );
195        assert_eq!(
196            mul_montgomery_form::<{ Modulus256::LIMBS }>(
197                &Uint::ONE,
198                &Modulus256::PARAMS.one,
199                &Modulus256::PARAMS.modulus,
200                Modulus256::PARAMS.mod_neg_inv()
201            ),
202            Uint::ONE
203        );
204    }
205
206    #[test]
207    fn monty_mul_r_r() {
208        // Multiply R by R and divide by R, which should equal R
209        assert_eq!(
210            mul_montgomery_form::<{ Modulus128::LIMBS }>(
211                &Modulus128::PARAMS.one,
212                &Modulus128::PARAMS.one,
213                &Modulus128::PARAMS.modulus,
214                Modulus128::PARAMS.mod_neg_inv()
215            ),
216            Modulus128::PARAMS.one
217        );
218        assert_eq!(
219            mul_montgomery_form::<{ Modulus256::LIMBS }>(
220                &Modulus256::PARAMS.one,
221                &Modulus256::PARAMS.one,
222                &Modulus256::PARAMS.modulus,
223                Modulus256::PARAMS.mod_neg_inv()
224            ),
225            Modulus256::PARAMS.one
226        );
227    }
228
229    #[test]
230    fn monty_square_r() {
231        // Square R and divide by R, which should equal R
232        assert_eq!(
233            square_montgomery_form::<{ Modulus128::LIMBS }>(
234                &Modulus128::PARAMS.one,
235                &Modulus128::PARAMS.modulus,
236                Modulus128::PARAMS.mod_neg_inv()
237            ),
238            Modulus128::PARAMS.one
239        );
240        assert_eq!(
241            square_montgomery_form::<{ Modulus256::LIMBS }>(
242                &Modulus256::PARAMS.one,
243                &Modulus256::PARAMS.modulus,
244                Modulus256::PARAMS.mod_neg_inv()
245            ),
246            Modulus256::PARAMS.one
247        );
248    }
249
250    #[test]
251    fn monty_mul_r2() {
252        // Multiply 1 by R2 and divide by R, which should equal R
253        assert_eq!(
254            mul_montgomery_form::<{ Modulus128::LIMBS }>(
255                &Uint::ONE,
256                &Modulus128::PARAMS.r2,
257                &Modulus128::PARAMS.modulus,
258                Modulus128::PARAMS.mod_neg_inv()
259            ),
260            Modulus128::PARAMS.one
261        );
262        assert_eq!(
263            mul_montgomery_form::<{ Modulus256::LIMBS }>(
264                &Uint::ONE,
265                &Modulus256::PARAMS.r2,
266                &Modulus256::PARAMS.modulus,
267                Modulus256::PARAMS.mod_neg_inv()
268            ),
269            Modulus256::PARAMS.one
270        );
271    }
272
273    #[test]
274    fn monty_mul_xr() {
275        // Reducing xR should return x
276        let x =
277            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
278        assert_eq!(
279            mul_montgomery_form::<{ Modulus256::LIMBS }>(
280                &x,
281                &Modulus256::PARAMS.one,
282                &Modulus256::PARAMS.modulus,
283                Modulus256::PARAMS.mod_neg_inv()
284            ),
285            x
286        );
287    }
288
289    #[test]
290    fn monty_mul_xr2() {
291        let x =
292            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
293
294        // Computing xR mod modulus without Montgomery reduction
295        let (lo, hi) = x.widening_mul(&Modulus256::PARAMS.one);
296        let c = lo.concat(&hi);
297        let red =
298            c.rem_vartime(&NonZero::new(Modulus256::PARAMS.modulus.0.concat(&U256::ZERO)).unwrap());
299        let (lo, hi) = red.split();
300        assert_eq!(hi, Uint::ZERO);
301
302        // Reducing xR^2 should return xR
303        assert_eq!(
304            mul_montgomery_form::<{ Modulus256::LIMBS }>(
305                &x,
306                &Modulus256::PARAMS.r2,
307                &Modulus256::PARAMS.modulus,
308                Modulus256::PARAMS.mod_neg_inv()
309            ),
310            lo
311        );
312    }
313
314    #[test]
315    fn test_new_retrieve() {
316        let x =
317            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
318        let x_mod = ConstMontyForm::<Modulus256, { Modulus256::LIMBS }>::new(&x);
319
320        // Confirm that when creating a Modular and retrieving the value, that it equals the original
321        assert_eq!(x, x_mod.retrieve());
322    }
323}
crypto_bigint/modular.rs

crypto_bigint/
modular.rs
