crypto_bigint/uint/
sub_mod.rs

1//! [`Uint`] subtraction modulus operations.
2
3use crate::{Limb, SubMod, Uint};
4
5impl<const LIMBS: usize> Uint<LIMBS> {
6    /// Computes `self - rhs mod p`.
7    ///
8    /// Assumes `self - rhs` as unbounded signed integer is in `[-p, p)`.
9    pub const fn sub_mod(&self, rhs: &Uint<LIMBS>, p: &Uint<LIMBS>) -> Uint<LIMBS> {
10        let (out, borrow) = self.sbb(rhs, Limb::ZERO);
11
12        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
13        // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
14        let mask = Uint::from_words([borrow.0; LIMBS]);
15
16        out.wrapping_add(&p.bitand(&mask))
17    }
18
19    /// Returns `(self..., carry) - (rhs...) mod (p...)`, where `carry <= 1`.
20    /// Assumes `-(p...) <= (self..., carry) - (rhs...) < (p...)`.
21    #[inline(always)]
22    pub(crate) const fn sub_mod_with_carry(&self, carry: Limb, rhs: &Self, p: &Self) -> Self {
23        debug_assert!(carry.0 <= 1);
24
25        let (out, borrow) = self.sbb(rhs, Limb::ZERO);
26
27        // The new `borrow = Word::MAX` iff `carry == 0` and `borrow == Word::MAX`.
28        let borrow = (!carry.0.wrapping_neg()) & borrow.0;
29
30        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
31        // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
32        let mask = Uint::from_words([borrow; LIMBS]);
33
34        out.wrapping_add(&p.bitand(&mask))
35    }
36
37    /// Computes `self - rhs mod p` for the special modulus
38    /// `p = MAX+1-c` where `c` is small enough to fit in a single [`Limb`].
39    ///
40    /// Assumes `self - rhs` as unbounded signed integer is in `[-p, p)`.
41    pub const fn sub_mod_special(&self, rhs: &Self, c: Limb) -> Self {
42        let (out, borrow) = self.sbb(rhs, Limb::ZERO);
43
44        // If underflow occurred, then we need to subtract `c` to account for
45        // the underflow. This cannot underflow due to the assumption
46        // `self - rhs >= -p`.
47        let l = borrow.0 & c.0;
48        out.wrapping_sub(&Uint::from_word(l))
49    }
50}
51
52impl<const LIMBS: usize> SubMod for Uint<LIMBS> {
53    type Output = Self;
54
55    fn sub_mod(&self, rhs: &Self, p: &Self) -> Self {
56        debug_assert!(self < p);
57        debug_assert!(rhs < p);
58        self.sub_mod(rhs, p)
59    }
60}
61
62#[cfg(all(test, feature = "rand"))]
63mod tests {
64    use crate::{Limb, NonZero, Random, RandomMod, Uint};
65    use rand_core::SeedableRng;
66
67    macro_rules! test_sub_mod {
68        ($size:expr, $test_name:ident) => {
69            #[test]
70            fn $test_name() {
71                let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
72                let moduli = [
73                    NonZero::<Uint<$size>>::random(&mut rng),
74                    NonZero::<Uint<$size>>::random(&mut rng),
75                ];
76
77                for p in &moduli {
78                    let base_cases = [
79                        (1u64, 0u64, 1u64.into()),
80                        (0, 1, p.wrapping_sub(&1u64.into())),
81                        (0, 0, 0u64.into()),
82                    ];
83                    for (a, b, c) in &base_cases {
84                        let a: Uint<$size> = (*a).into();
85                        let b: Uint<$size> = (*b).into();
86
87                        let x = a.sub_mod(&b, p);
88                        assert_eq!(*c, x, "{} - {} mod {} = {} != {}", a, b, p, x, c);
89                    }
90
91                    if $size > 1 {
92                        for _i in 0..100 {
93                            let a: Uint<$size> = Limb::random(&mut rng).into();
94                            let b: Uint<$size> = Limb::random(&mut rng).into();
95                            let (a, b) = if a < b { (b, a) } else { (a, b) };
96
97                            let c = a.sub_mod(&b, p);
98                            assert!(c < **p, "not reduced");
99                            assert_eq!(c, a.wrapping_sub(&b), "result incorrect");
100                        }
101                    }
102
103                    for _i in 0..100 {
104                        let a = Uint::<$size>::random_mod(&mut rng, p);
105                        let b = Uint::<$size>::random_mod(&mut rng, p);
106
107                        let c = a.sub_mod(&b, p);
108                        assert!(c < **p, "not reduced: {} >= {} ", c, p);
109
110                        let x = a.wrapping_sub(&b);
111                        if a >= b && x < **p {
112                            assert_eq!(c, x, "incorrect result");
113                        }
114                    }
115                }
116            }
117        };
118    }
119
120    macro_rules! test_sub_mod_special {
121        ($size:expr, $test_name:ident) => {
122            #[test]
123            fn $test_name() {
124                let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
125                let moduli = [
126                    NonZero::<Limb>::random(&mut rng),
127                    NonZero::<Limb>::random(&mut rng),
128                ];
129
130                for special in &moduli {
131                    let p = &NonZero::new(Uint::ZERO.wrapping_sub(&Uint::from_word(special.0)))
132                        .unwrap();
133
134                    let minus_one = p.wrapping_sub(&Uint::ONE);
135
136                    let base_cases = [
137                        (Uint::ZERO, Uint::ZERO, Uint::ZERO),
138                        (Uint::ONE, Uint::ZERO, Uint::ONE),
139                        (Uint::ZERO, Uint::ONE, minus_one),
140                        (minus_one, minus_one, Uint::ZERO),
141                        (Uint::ZERO, minus_one, Uint::ONE),
142                    ];
143                    for (a, b, c) in &base_cases {
144                        let x = a.sub_mod_special(&b, *special.as_ref());
145                        assert_eq!(*c, x, "{} - {} mod {} = {} != {}", a, b, p, x, c);
146                    }
147
148                    for _i in 0..100 {
149                        let a = Uint::<$size>::random_mod(&mut rng, p);
150                        let b = Uint::<$size>::random_mod(&mut rng, p);
151
152                        let c = a.sub_mod_special(&b, *special.as_ref());
153                        assert!(c < **p, "not reduced: {} >= {} ", c, p);
154
155                        let expected = a.sub_mod(&b, p);
156                        assert_eq!(c, expected, "incorrect result");
157                    }
158                }
159            }
160        };
161    }
162
163    // Test requires 1-limb is capable of representing a 64-bit integer
164    #[cfg(target_pointer_width = "64")]
165    test_sub_mod!(1, sub1);
166
167    test_sub_mod!(2, sub2);
168    test_sub_mod!(3, sub3);
169    test_sub_mod!(4, sub4);
170    test_sub_mod!(5, sub5);
171    test_sub_mod!(6, sub6);
172    test_sub_mod!(7, sub7);
173    test_sub_mod!(8, sub8);
174    test_sub_mod!(9, sub9);
175    test_sub_mod!(10, sub10);
176    test_sub_mod!(11, sub11);
177    test_sub_mod!(12, sub12);
178
179    test_sub_mod_special!(1, sub_mod_special_1);
180    test_sub_mod_special!(2, sub_mod_special_2);
181    test_sub_mod_special!(3, sub_mod_special_3);
182    test_sub_mod_special!(4, sub_mod_special_4);
183    test_sub_mod_special!(5, sub_mod_special_5);
184    test_sub_mod_special!(6, sub_mod_special_6);
185    test_sub_mod_special!(7, sub_mod_special_7);
186    test_sub_mod_special!(8, sub_mod_special_8);
187    test_sub_mod_special!(9, sub_mod_special_9);
188    test_sub_mod_special!(10, sub_mod_special_10);
189    test_sub_mod_special!(11, sub_mod_special_11);
190    test_sub_mod_special!(12, sub_mod_special_12);
191}
crypto_bigint/uint/sub_mod.rs

crypto_bigint/uint/
sub_mod.rs
