crypto_bigint/uint/
modular.rs

1mod reduction;
2
3/// Implements `Residue`s, supporting modular arithmetic with a constant modulus.
4pub mod constant_mod;
5/// Implements `DynResidue`s, supporting modular arithmetic with a modulus set at runtime.
6pub mod runtime_mod;
7
8mod add;
9mod div_by_2;
10mod inv;
11mod mul;
12mod pow;
13mod sub;
14
15pub use reduction::montgomery_reduction;
16
17/// A generalization for numbers kept in optimized representations (e.g. Montgomery)
18/// that can be converted back to the original form.
19pub trait Retrieve {
20    /// The original type.
21    type Output;
22
23    /// Convert the number back from the optimized representation.
24    fn retrieve(&self) -> Self::Output;
25}
26
27#[cfg(test)]
28mod tests {
29    use crate::{
30        const_residue, impl_modulus,
31        modular::{
32            constant_mod::Residue, constant_mod::ResidueParams, reduction::montgomery_reduction,
33        },
34        NonZero, Uint, U256, U64,
35    };
36
37    impl_modulus!(
38        Modulus1,
39        U256,
40        "73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001"
41    );
42
43    #[test]
44    fn test_montgomery_params() {
45        assert_eq!(
46            Modulus1::R,
47            U256::from_be_hex("1824b159acc5056f998c4fefecbc4ff55884b7fa0003480200000001fffffffe")
48        );
49        assert_eq!(
50            Modulus1::R2,
51            U256::from_be_hex("0748d9d99f59ff1105d314967254398f2b6cedcb87925c23c999e990f3f29c6d")
52        );
53        assert_eq!(
54            Modulus1::MOD_NEG_INV,
55            U64::from_be_hex("fffffffeffffffff").limbs[0]
56        );
57    }
58
59    impl_modulus!(
60        Modulus2,
61        U256,
62        "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"
63    );
64
65    #[test]
66    fn test_reducing_r() {
67        // Divide the value R by R, which should equal 1
68        assert_eq!(
69            montgomery_reduction::<{ Modulus2::LIMBS }>(
70                &(Modulus2::R, Uint::ZERO),
71                &Modulus2::MODULUS,
72                Modulus2::MOD_NEG_INV
73            ),
74            Uint::ONE
75        );
76    }
77
78    #[test]
79    fn test_reducing_r2() {
80        // Divide the value R^2 by R, which should equal R
81        assert_eq!(
82            montgomery_reduction::<{ Modulus2::LIMBS }>(
83                &(Modulus2::R2, Uint::ZERO),
84                &Modulus2::MODULUS,
85                Modulus2::MOD_NEG_INV
86            ),
87            Modulus2::R
88        );
89    }
90
91    #[test]
92    fn test_reducing_r2_wide() {
93        // Divide the value R^2 by R, which should equal R
94        let (hi, lo) = Modulus2::R.square().split();
95        assert_eq!(
96            montgomery_reduction::<{ Modulus2::LIMBS }>(
97                &(lo, hi),
98                &Modulus2::MODULUS,
99                Modulus2::MOD_NEG_INV
100            ),
101            Modulus2::R
102        );
103    }
104
105    #[test]
106    fn test_reducing_xr_wide() {
107        // Reducing xR should return x
108        let x =
109            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
110        let product = x.mul_wide(&Modulus2::R);
111        assert_eq!(
112            montgomery_reduction::<{ Modulus2::LIMBS }>(
113                &product,
114                &Modulus2::MODULUS,
115                Modulus2::MOD_NEG_INV
116            ),
117            x
118        );
119    }
120
121    #[test]
122    fn test_reducing_xr2_wide() {
123        // Reducing xR^2 should return xR
124        let x =
125            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
126        let product = x.mul_wide(&Modulus2::R2);
127
128        // Computing xR mod modulus without Montgomery reduction
129        let (lo, hi) = x.mul_wide(&Modulus2::R);
130        let c = hi.concat(&lo);
131        let red = c.rem(&NonZero::new(U256::ZERO.concat(&Modulus2::MODULUS)).unwrap());
132        let (hi, lo) = red.split();
133        assert_eq!(hi, Uint::ZERO);
134
135        assert_eq!(
136            montgomery_reduction::<{ Modulus2::LIMBS }>(
137                &product,
138                &Modulus2::MODULUS,
139                Modulus2::MOD_NEG_INV
140            ),
141            lo
142        );
143    }
144
145    #[test]
146    fn test_new_retrieve() {
147        let x =
148            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
149        let x_mod = Residue::<Modulus2, { Modulus2::LIMBS }>::new(&x);
150
151        // Confirm that when creating a Modular and retrieving the value, that it equals the original
152        assert_eq!(x, x_mod.retrieve());
153    }
154
155    #[test]
156    fn test_residue_macro() {
157        let x =
158            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
159        assert_eq!(
160            Residue::<Modulus2, { Modulus2::LIMBS }>::new(&x),
161            const_residue!(x, Modulus2)
162        );
163    }
164}
crypto_bigint/uint/modular.rs

crypto_bigint/uint/
modular.rs
