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 where the
9//! modulus is fixed at compile-time.
10//!
11//! The [`impl_modulus!`][`crate::impl_modulus`] macro can be used to define a compile-time modulus,
12//! whereas the [`const_monty_form!`][`crate::const_monty_form`] macro can define a [`ConstMontyForm`] constant.
13//!
14//! # Dynamic moduli chosen at runtime
15//!
16//! The [`MontyForm`] and [`MontyParams`] types implement support for modular arithmetic where
17//! the modulus can vary at runtime.
18
19mod const_monty_form;
20mod lincomb;
21mod monty_form;
22mod reduction;
23
24mod add;
25mod div_by_2;
26mod mul;
27mod pow;
28pub(crate) mod safegcd;
29mod sub;
30
31#[cfg(feature = "alloc")]
32pub(crate) mod boxed_monty_form;
33
34pub use self::{
35    const_monty_form::{inv::ConstMontyFormInverter, ConstMontyForm, ConstMontyParams},
36    monty_form::{inv::MontyFormInverter, MontyForm, MontyParams},
37    reduction::montgomery_reduction,
38    safegcd::SafeGcdInverter,
39};
40
41#[cfg(feature = "alloc")]
42pub use self::{
43    boxed_monty_form::{BoxedMontyForm, BoxedMontyParams},
44    safegcd::boxed::BoxedSafeGcdInverter,
45};
46
47/// A generalization for numbers kept in optimized representations (e.g. Montgomery)
48/// that can be converted back to the original form.
49pub trait Retrieve {
50    /// The original type.
51    type Output;
52
53    /// Convert the number back from the optimized representation.
54    fn retrieve(&self) -> Self::Output;
55}
56
57#[cfg(test)]
58mod tests {
59    use crate::{
60        const_monty_form, impl_modulus,
61        modular::{
62            const_monty_form::{ConstMontyForm, ConstMontyParams},
63            reduction::montgomery_reduction,
64        },
65        NonZero, Uint, U256, U64,
66    };
67
68    impl_modulus!(
69        Modulus1,
70        U256,
71        "73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001"
72    );
73
74    #[test]
75    fn test_montgomery_params() {
76        assert_eq!(
77            Modulus1::ONE,
78            U256::from_be_hex("1824b159acc5056f998c4fefecbc4ff55884b7fa0003480200000001fffffffe")
79        );
80        assert_eq!(
81            Modulus1::R2,
82            U256::from_be_hex("0748d9d99f59ff1105d314967254398f2b6cedcb87925c23c999e990f3f29c6d")
83        );
84        assert_eq!(
85            Modulus1::MOD_NEG_INV,
86            U64::from_be_hex("fffffffeffffffff").limbs[0]
87        );
88    }
89
90    impl_modulus!(
91        Modulus2,
92        U256,
93        "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"
94    );
95
96    #[test]
97    fn test_reducing_one() {
98        // Divide the value R by R, which should equal 1
99        assert_eq!(
100            montgomery_reduction::<{ Modulus2::LIMBS }>(
101                &(Modulus2::ONE, Uint::ZERO),
102                &Modulus2::MODULUS,
103                Modulus2::MOD_NEG_INV
104            ),
105            Uint::ONE
106        );
107    }
108
109    #[test]
110    fn test_reducing_r2() {
111        // Divide the value R^2 by R, which should equal R
112        assert_eq!(
113            montgomery_reduction::<{ Modulus2::LIMBS }>(
114                &(Modulus2::R2, Uint::ZERO),
115                &Modulus2::MODULUS,
116                Modulus2::MOD_NEG_INV
117            ),
118            Modulus2::ONE
119        );
120    }
121
122    #[test]
123    fn test_reducing_r2_wide() {
124        // Divide the value ONE^2 by R, which should equal ONE
125        let (lo, hi) = Modulus2::ONE.square().split();
126        assert_eq!(
127            montgomery_reduction::<{ Modulus2::LIMBS }>(
128                &(lo, hi),
129                &Modulus2::MODULUS,
130                Modulus2::MOD_NEG_INV
131            ),
132            Modulus2::ONE
133        );
134    }
135
136    #[test]
137    fn test_reducing_xr_wide() {
138        // Reducing xR should return x
139        let x =
140            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
141        let product = x.split_mul(&Modulus2::ONE);
142        assert_eq!(
143            montgomery_reduction::<{ Modulus2::LIMBS }>(
144                &product,
145                &Modulus2::MODULUS,
146                Modulus2::MOD_NEG_INV
147            ),
148            x
149        );
150    }
151
152    #[test]
153    fn test_reducing_xr2_wide() {
154        // Reducing xR^2 should return xR
155        let x =
156            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
157        let product = x.split_mul(&Modulus2::R2);
158
159        // Computing xR mod modulus without Montgomery reduction
160        let (lo, hi) = x.split_mul(&Modulus2::ONE);
161        let c = lo.concat(&hi);
162        let red = c.rem_vartime(&NonZero::new(Modulus2::MODULUS.0.concat(&U256::ZERO)).unwrap());
163        let (lo, hi) = red.split();
164        assert_eq!(hi, Uint::ZERO);
165
166        assert_eq!(
167            montgomery_reduction::<{ Modulus2::LIMBS }>(
168                &product,
169                &Modulus2::MODULUS,
170                Modulus2::MOD_NEG_INV
171            ),
172            lo
173        );
174    }
175
176    #[test]
177    fn test_new_retrieve() {
178        let x =
179            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
180        let x_mod = ConstMontyForm::<Modulus2, { Modulus2::LIMBS }>::new(&x);
181
182        // Confirm that when creating a Modular and retrieving the value, that it equals the original
183        assert_eq!(x, x_mod.retrieve());
184    }
185
186    #[test]
187    fn test_const_monty_form_macro() {
188        let x =
189            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
190        assert_eq!(
191            ConstMontyForm::<Modulus2, { Modulus2::LIMBS }>::new(&x),
192            const_monty_form!(x, Modulus2)
193        );
194    }
195}
crypto_bigint/modular.rs

crypto_bigint/
modular.rs
