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 = c.rem_vartime(
169            &NonZero::new(Modulus256::PARAMS.modulus.as_ref().concat(&U256::ZERO)).unwrap(),
170        );
171        let (lo, hi) = red.split();
172        assert_eq!(hi, Uint::ZERO);
173
174        assert_eq!(
175            montgomery_reduction::<{ Modulus256::LIMBS }>(
176                &product,
177                &Modulus256::PARAMS.modulus,
178                Modulus256::PARAMS.mod_neg_inv()
179            ),
180            lo
181        );
182    }
183
184    #[test]
185    fn monty_mul_one_r() {
186        // Multiply 1 by R and divide by R, which should equal 1
187        assert_eq!(
188            mul_montgomery_form::<{ Modulus128::LIMBS }>(
189                &Uint::ONE,
190                &Modulus128::PARAMS.one,
191                &Modulus128::PARAMS.modulus,
192                Modulus128::PARAMS.mod_neg_inv()
193            ),
194            Uint::ONE
195        );
196        assert_eq!(
197            mul_montgomery_form::<{ Modulus256::LIMBS }>(
198                &Uint::ONE,
199                &Modulus256::PARAMS.one,
200                &Modulus256::PARAMS.modulus,
201                Modulus256::PARAMS.mod_neg_inv()
202            ),
203            Uint::ONE
204        );
205    }
206
207    #[test]
208    fn monty_mul_r_r() {
209        // Multiply R by R and divide by R, which should equal R
210        assert_eq!(
211            mul_montgomery_form::<{ Modulus128::LIMBS }>(
212                &Modulus128::PARAMS.one,
213                &Modulus128::PARAMS.one,
214                &Modulus128::PARAMS.modulus,
215                Modulus128::PARAMS.mod_neg_inv()
216            ),
217            Modulus128::PARAMS.one
218        );
219        assert_eq!(
220            mul_montgomery_form::<{ Modulus256::LIMBS }>(
221                &Modulus256::PARAMS.one,
222                &Modulus256::PARAMS.one,
223                &Modulus256::PARAMS.modulus,
224                Modulus256::PARAMS.mod_neg_inv()
225            ),
226            Modulus256::PARAMS.one
227        );
228    }
229
230    #[test]
231    fn monty_square_r() {
232        // Square R and divide by R, which should equal R
233        assert_eq!(
234            square_montgomery_form::<{ Modulus128::LIMBS }>(
235                &Modulus128::PARAMS.one,
236                &Modulus128::PARAMS.modulus,
237                Modulus128::PARAMS.mod_neg_inv()
238            ),
239            Modulus128::PARAMS.one
240        );
241        assert_eq!(
242            square_montgomery_form::<{ Modulus256::LIMBS }>(
243                &Modulus256::PARAMS.one,
244                &Modulus256::PARAMS.modulus,
245                Modulus256::PARAMS.mod_neg_inv()
246            ),
247            Modulus256::PARAMS.one
248        );
249    }
250
251    #[test]
252    fn monty_mul_r2() {
253        // Multiply 1 by R2 and divide by R, which should equal R
254        assert_eq!(
255            mul_montgomery_form::<{ Modulus128::LIMBS }>(
256                &Uint::ONE,
257                &Modulus128::PARAMS.r2,
258                &Modulus128::PARAMS.modulus,
259                Modulus128::PARAMS.mod_neg_inv()
260            ),
261            Modulus128::PARAMS.one
262        );
263        assert_eq!(
264            mul_montgomery_form::<{ Modulus256::LIMBS }>(
265                &Uint::ONE,
266                &Modulus256::PARAMS.r2,
267                &Modulus256::PARAMS.modulus,
268                Modulus256::PARAMS.mod_neg_inv()
269            ),
270            Modulus256::PARAMS.one
271        );
272    }
273
274    #[test]
275    fn monty_mul_xr() {
276        // Reducing xR should return x
277        let x =
278            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
279        assert_eq!(
280            mul_montgomery_form::<{ Modulus256::LIMBS }>(
281                &x,
282                &Modulus256::PARAMS.one,
283                &Modulus256::PARAMS.modulus,
284                Modulus256::PARAMS.mod_neg_inv()
285            ),
286            x
287        );
288    }
289
290    #[test]
291    fn monty_mul_xr2() {
292        let x =
293            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
294
295        // Computing xR mod modulus without Montgomery reduction
296        let (lo, hi) = x.widening_mul(&Modulus256::PARAMS.one);
297        let c = lo.concat(&hi);
298        let red = c.rem_vartime(
299            &NonZero::new(Modulus256::PARAMS.modulus.as_ref().concat(&U256::ZERO)).unwrap(),
300        );
301        let (lo, hi) = red.split();
302        assert_eq!(hi, Uint::ZERO);
303
304        // Reducing xR^2 should return xR
305        assert_eq!(
306            mul_montgomery_form::<{ Modulus256::LIMBS }>(
307                &x,
308                &Modulus256::PARAMS.r2,
309                &Modulus256::PARAMS.modulus,
310                Modulus256::PARAMS.mod_neg_inv()
311            ),
312            lo
313        );
314    }
315
316    #[test]
317    fn test_new_retrieve() {
318        let x =
319            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
320        let x_mod = ConstMontyForm::<Modulus256, { Modulus256::LIMBS }>::new(&x);
321
322        // Confirm that when creating a Modular and retrieving the value, that it equals the original
323        assert_eq!(x, x_mod.retrieve());
324    }
325}
crypto_bigint/modular.rs

crypto_bigint/
modular.rs
