crypto_bigint/uint/boxed/
sub_mod.rs

1//! [`BoxedUint`] modular subtraction operations.
2
3use crate::{BoxedUint, Limb, SubMod, Zero};
4
5impl BoxedUint {
6    /// Computes `self - rhs mod p`.
7    ///
8    /// Assumes `self - rhs` as unbounded signed integer is in `[-p, p)`.
9    pub fn sub_mod(&self, rhs: &Self, p: &Self) -> Self {
10        debug_assert_eq!(self.bits_precision(), p.bits_precision());
11        debug_assert_eq!(rhs.bits_precision(), p.bits_precision());
12        debug_assert!(self < p);
13        debug_assert!(rhs < p);
14
15        let (mut out, borrow) = self.sbb(rhs, Limb::ZERO);
16
17        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
18        // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
19        out.conditional_adc_assign(p, !borrow.is_zero());
20        out
21    }
22
23    /// Returns `(self..., carry) - (rhs...) mod (p...)`, where `carry <= 1`.
24    /// Assumes `-(p...) <= (self..., carry) - (rhs...) < (p...)`.
25    #[inline(always)]
26    pub(crate) fn sub_assign_mod_with_carry(&mut self, carry: Limb, rhs: &Self, p: &Self) {
27        debug_assert!(carry.0 <= 1);
28
29        let borrow = self.sbb_assign(rhs, Limb::ZERO);
30
31        // The new `borrow = Word::MAX` iff `carry == 0` and `borrow == Word::MAX`.
32        let mask = carry.wrapping_neg().not().bitand(borrow);
33
34        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
35        // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
36        self.conditional_adc_assign(p, !mask.is_zero());
37    }
38
39    /// Computes `self - rhs mod p` for the special modulus
40    /// `p = MAX+1-c` where `c` is small enough to fit in a single [`Limb`].
41    ///
42    /// Assumes `self - rhs` as unbounded signed integer is in `[-p, p)`.
43    pub fn sub_mod_special(&self, rhs: &Self, c: Limb) -> Self {
44        let (out, borrow) = self.sbb(rhs, Limb::ZERO);
45
46        // If underflow occurred, then we need to subtract `c` to account for
47        // the underflow. This cannot underflow due to the assumption
48        // `self - rhs >= -p`.
49        let l = borrow.0 & c.0;
50        out.wrapping_sub(&Self::from(l))
51    }
52}
53
54impl SubMod for BoxedUint {
55    type Output = Self;
56
57    fn sub_mod(&self, rhs: &Self, p: &Self) -> Self {
58        self.sub_mod(rhs, p)
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use super::BoxedUint;
65    use hex_literal::hex;
66
67    #[test]
68    fn sub_mod_nist_p256() {
69        let a = BoxedUint::from_be_slice(
70            &hex!("1a2472fde50286541d97ca6a3592dd75beb9c9646e40c511b82496cfc3926956"),
71            256,
72        )
73        .unwrap();
74        let b = BoxedUint::from_be_slice(
75            &hex!("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251"),
76            256,
77        )
78        .unwrap();
79        let n = BoxedUint::from_be_slice(
80            &hex!("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"),
81            256,
82        )
83        .unwrap();
84
85        let actual = a.sub_mod(&b, &n);
86        let expected = BoxedUint::from_be_slice(
87            &hex!("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56"),
88            256,
89        )
90        .unwrap();
91
92        assert_eq!(expected, actual);
93    }
94}
crypto_bigint/uint/boxed/sub_mod.rs

crypto_bigint/uint/boxed/
sub_mod.rs
