crypto_bigint/uint/boxed/
mul.rs

1//! [`BoxedUint`] multiplication operations.
2
3use crate::{
4    uint::mul::{
5        karatsuba::{karatsuba_mul_limbs, karatsuba_square_limbs, KARATSUBA_MIN_STARTING_LIMBS},
6        mul_limbs, square_limbs,
7    },
8    BoxedUint, CheckedMul, Limb, WideningMul, Wrapping, WrappingMul, Zero,
9};
10use core::ops::{Mul, MulAssign};
11use subtle::{Choice, CtOption};
12
13impl BoxedUint {
14    /// Multiply `self` by `rhs`.
15    ///
16    /// Returns a widened output with a limb count equal to the sums of the input limb counts.
17    pub fn mul(&self, rhs: &Self) -> Self {
18        let size = self.nlimbs() + rhs.nlimbs();
19        let overlap = self.nlimbs().min(rhs.nlimbs());
20
21        if self.nlimbs().min(rhs.nlimbs()) >= KARATSUBA_MIN_STARTING_LIMBS {
22            let mut limbs = vec![Limb::ZERO; size + overlap * 2];
23            let (out, scratch) = limbs.as_mut_slice().split_at_mut(size);
24            karatsuba_mul_limbs(&self.limbs, &rhs.limbs, out, scratch);
25            limbs.truncate(size);
26            return limbs.into();
27        }
28
29        let mut limbs = vec![Limb::ZERO; size];
30        mul_limbs(&self.limbs, &rhs.limbs, &mut limbs);
31        limbs.into()
32    }
33
34    /// Perform wrapping multiplication, wrapping to the width of `self`.
35    pub fn wrapping_mul(&self, rhs: &Self) -> Self {
36        self.mul(rhs).shorten(self.bits_precision())
37    }
38
39    /// Multiply `self` by itself.
40    pub fn square(&self) -> Self {
41        let size = self.nlimbs() * 2;
42
43        if self.nlimbs() >= KARATSUBA_MIN_STARTING_LIMBS * 2 {
44            let mut limbs = vec![Limb::ZERO; size * 2];
45            let (out, scratch) = limbs.as_mut_slice().split_at_mut(size);
46            karatsuba_square_limbs(&self.limbs, out, scratch);
47            limbs.truncate(size);
48            return limbs.into();
49        }
50
51        let mut limbs = vec![Limb::ZERO; size];
52        square_limbs(&self.limbs, &mut limbs);
53        limbs.into()
54    }
55}
56
57impl CheckedMul for BoxedUint {
58    fn checked_mul(&self, rhs: &BoxedUint) -> CtOption<Self> {
59        let product = self.mul(rhs);
60
61        // Ensure high limbs are all zero
62        let is_some = product.limbs[self.nlimbs()..]
63            .iter()
64            .fold(Choice::from(1), |choice, limb| choice & limb.is_zero());
65
66        let mut limbs = product.limbs.into_vec();
67        limbs.truncate(self.nlimbs());
68        CtOption::new(limbs.into(), is_some)
69    }
70}
71
72impl Mul<BoxedUint> for BoxedUint {
73    type Output = BoxedUint;
74
75    fn mul(self, rhs: BoxedUint) -> Self {
76        BoxedUint::mul(&self, &rhs)
77    }
78}
79
80impl Mul<&BoxedUint> for BoxedUint {
81    type Output = BoxedUint;
82
83    fn mul(self, rhs: &BoxedUint) -> Self {
84        BoxedUint::mul(&self, rhs)
85    }
86}
87
88impl Mul<BoxedUint> for &BoxedUint {
89    type Output = BoxedUint;
90
91    fn mul(self, rhs: BoxedUint) -> Self::Output {
92        BoxedUint::mul(self, &rhs)
93    }
94}
95
96impl Mul<&BoxedUint> for &BoxedUint {
97    type Output = BoxedUint;
98
99    fn mul(self, rhs: &BoxedUint) -> Self::Output {
100        self.checked_mul(rhs)
101            .expect("attempted to multiply with overflow")
102    }
103}
104
105impl MulAssign<BoxedUint> for BoxedUint {
106    fn mul_assign(&mut self, rhs: BoxedUint) {
107        self.mul_assign(&rhs)
108    }
109}
110
111impl MulAssign<&BoxedUint> for BoxedUint {
112    fn mul_assign(&mut self, rhs: &BoxedUint) {
113        *self = self.clone().mul(rhs)
114    }
115}
116
117impl MulAssign<Wrapping<BoxedUint>> for Wrapping<BoxedUint> {
118    fn mul_assign(&mut self, other: Wrapping<BoxedUint>) {
119        *self = Wrapping(self.0.wrapping_mul(&other.0));
120    }
121}
122
123impl MulAssign<&Wrapping<BoxedUint>> for Wrapping<BoxedUint> {
124    fn mul_assign(&mut self, other: &Wrapping<BoxedUint>) {
125        *self = Wrapping(self.0.wrapping_mul(&other.0));
126    }
127}
128
129impl WideningMul for BoxedUint {
130    type Output = Self;
131
132    #[inline]
133    fn widening_mul(&self, rhs: BoxedUint) -> Self {
134        self.mul(&rhs)
135    }
136}
137
138impl WideningMul<&BoxedUint> for BoxedUint {
139    type Output = Self;
140
141    #[inline]
142    fn widening_mul(&self, rhs: &BoxedUint) -> Self {
143        self.mul(rhs)
144    }
145}
146
147impl WrappingMul for BoxedUint {
148    fn wrapping_mul(&self, v: &Self) -> Self {
149        self.wrapping_mul(v)
150    }
151}
152
153#[cfg(test)]
154mod tests {
155    use crate::BoxedUint;
156
157    #[test]
158    fn mul_zero_and_one() {
159        assert!(bool::from(
160            BoxedUint::zero().mul(&BoxedUint::zero()).is_zero()
161        ));
162        assert!(bool::from(
163            BoxedUint::zero().mul(&BoxedUint::one()).is_zero()
164        ));
165        assert!(bool::from(
166            BoxedUint::one().mul(&BoxedUint::zero()).is_zero()
167        ));
168        assert_eq!(BoxedUint::one().mul(&BoxedUint::one()), BoxedUint::one());
169    }
170
171    #[test]
172    fn mul_primes() {
173        let primes: &[u32] = &[3, 5, 17, 257, 65537];
174
175        for &a_int in primes {
176            for &b_int in primes {
177                let actual = BoxedUint::from(a_int).mul(&BoxedUint::from(b_int));
178                let expected = BoxedUint::from(a_int as u64 * b_int as u64);
179                assert_eq!(actual, expected);
180            }
181        }
182    }
183
184    #[cfg(feature = "rand_core")]
185    #[test]
186    fn mul_cmp() {
187        use crate::RandomBits;
188        use rand_core::SeedableRng;
189        let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
190
191        for _ in 0..50 {
192            let a = BoxedUint::random_bits(&mut rng, 4096);
193            assert_eq!(a.mul(&a), a.square(), "a = {a}");
194        }
195
196        for _ in 0..50 {
197            let a = BoxedUint::random_bits(&mut rng, 4096);
198            let b = BoxedUint::random_bits(&mut rng, 5000);
199            assert_eq!(a.mul(&b), b.mul(&a), "a={a}, b={b}");
200        }
201    }
202}
crypto_bigint/uint/boxed/mul.rs

crypto_bigint/uint/boxed/
mul.rs
