crypto_bigint/uint/
add_mod.rs

1//! [`Uint`] modular addition operations.
2
3use crate::{AddMod, Limb, NonZero, Uint};
4
5impl<const LIMBS: usize> Uint<LIMBS> {
6    /// Computes `self + rhs mod p`.
7    ///
8    /// Assumes `self + rhs` as unbounded integer is `< 2p`.
9    #[must_use]
10    pub const fn add_mod(&self, rhs: &Self, p: &NonZero<Self>) -> Self {
11        let (w, carry) = self.carrying_add(rhs, Limb::ZERO);
12        w.try_sub_with_carry(carry, p.as_ref()).0
13    }
14
15    /// Computes `self + rhs mod p` for the special modulus
16    /// `p = MAX+1-c` where `c` is small enough to fit in a single [`Limb`].
17    ///
18    /// Assumes `self + rhs` as unbounded integer is `< 2p`.
19    #[must_use]
20    pub const fn add_mod_special(&self, rhs: &Self, c: Limb) -> Self {
21        // `Uint::carrying_add` also works with a carry greater than 1.
22        let (out, carry) = self.carrying_add(rhs, c);
23
24        // If overflow occurred, then above addition of `c` already accounts
25        // for the overflow. Otherwise, we need to subtract `c` again, which
26        // in that case cannot underflow.
27        let l = carry.0.wrapping_sub(1) & c.0;
28        out.wrapping_sub(&Self::from_word(l))
29    }
30
31    /// Computes `self + self mod p`.
32    ///
33    /// Assumes `self` as unbounded integer is `< p`.
34    #[must_use]
35    pub const fn double_mod(&self, p: &NonZero<Self>) -> Self {
36        let (w, carry) = self.shl1_with_carry(Limb::ZERO);
37        w.try_sub_with_carry(carry, p.as_ref()).0
38    }
39}
40
41impl<const LIMBS: usize> AddMod for Uint<LIMBS> {
42    type Output = Self;
43
44    fn add_mod(&self, rhs: &Self, p: &NonZero<Self>) -> Self {
45        debug_assert!(self < p.as_ref());
46        debug_assert!(rhs < p.as_ref());
47        self.add_mod(rhs, p)
48    }
49}
50
51#[cfg(test)]
52mod tests {
53    use crate::U256;
54
55    #[cfg(feature = "rand_core")]
56    use crate::{Limb, NonZero, Random, RandomMod, Uint};
57    #[cfg(feature = "rand_core")]
58    use rand_core::SeedableRng;
59
60    #[test]
61    fn add_mod_nist_p256() {
62        let a =
63            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
64        let b =
65            U256::from_be_hex("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251");
66        let n =
67            U256::from_be_hex("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551")
68                .to_nz()
69                .unwrap();
70
71        let actual = a.add_mod(&b, &n);
72        let expected =
73            U256::from_be_hex("1a2472fde50286541d97ca6a3592dd75beb9c9646e40c511b82496cfc3926956");
74
75        assert_eq!(expected, actual);
76    }
77
78    #[test]
79    fn double_mod_expected() {
80        let a =
81            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
82        let n =
83            U256::from_be_hex("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551")
84                .to_nz()
85                .unwrap();
86
87        assert_eq!(a.add_mod(&a, &n), a.double_mod(&n));
88    }
89
90    #[cfg(feature = "rand_core")]
91    #[test]
92    fn add_mod_special() {
93        fn test_size<const LIMBS: usize>() {
94            let mut rng = chacha20::ChaCha8Rng::seed_from_u64(1);
95            let moduli = [
96                NonZero::<Limb>::random_from_rng(&mut rng),
97                NonZero::<Limb>::random_from_rng(&mut rng),
98            ];
99
100            for special in &moduli {
101                let p = &NonZero::new(Uint::ZERO.wrapping_sub(&Uint::from(special.get()))).unwrap();
102
103                let minus_one = p.wrapping_sub(&Uint::ONE);
104
105                let base_cases = [
106                    (Uint::ZERO, Uint::ZERO, Uint::ZERO),
107                    (Uint::ONE, Uint::ZERO, Uint::ONE),
108                    (Uint::ZERO, Uint::ONE, Uint::ONE),
109                    (minus_one, Uint::ONE, Uint::ZERO),
110                    (Uint::ONE, minus_one, Uint::ZERO),
111                ];
112                for (a, b, c) in &base_cases {
113                    let x = a.add_mod_special(b, *special.as_ref());
114                    assert_eq!(*c, x, "{} + {} mod {} = {} != {}", a, b, p, x, c);
115                }
116
117                for _i in 0..100 {
118                    let a = Uint::<LIMBS>::random_mod_vartime(&mut rng, p);
119                    let b = Uint::<LIMBS>::random_mod_vartime(&mut rng, p);
120
121                    let c = a.add_mod_special(&b, *special.as_ref());
122                    assert!(c < **p, "not reduced: {} >= {} ", c, p);
123
124                    let expected = a.add_mod(&b, p);
125                    assert_eq!(c, expected, "incorrect result");
126                }
127            }
128        }
129
130        test_size::<1>();
131        test_size::<2>();
132        test_size::<3>();
133        if cfg!(not(miri)) {
134            test_size::<4>();
135            test_size::<8>();
136            test_size::<16>();
137        }
138    }
139}
crypto_bigint/uint/add_mod.rs

crypto_bigint/uint/
add_mod.rs
