crypto_bigint/uint/boxed/
mul.rs

1//! [`BoxedUint`] multiplication operations.
2
3use crate::{
4    BoxedUint, CheckedMul, Choice, ConcatenatingMul, ConcatenatingSquare, CtOption, Limb, Mul,
5    MulAssign, UintRef, Wrapping, WrappingMul,
6};
7
8mod helper;
9pub(crate) use helper::BoxedMultiplier;
10
11impl BoxedUint {
12    /// Multiply `self` by `rhs`.
13    ///
14    /// Returns a widened output with a limb count equal to the sums of the input limb counts.
15    #[must_use]
16    #[deprecated(since = "0.7.0", note = "please use `concatenating_mul`")]
17    pub fn mul(&self, rhs: impl AsRef<UintRef>) -> Self {
18        self.concatenating_mul(rhs)
19    }
20
21    /// Perform wrapping multiplication, wrapping to the width of `self`.
22    #[must_use]
23    pub fn wrapping_mul(&self, rhs: impl AsRef<UintRef>) -> Self {
24        self.wrapping_mul_carry(rhs.as_ref(), self.nlimbs()).0
25    }
26
27    /// Multiply `self` by `rhs`, wrapping to the width of `self`.
28    /// Returns `CtOption::None` if the result overflowed the precision of `self`.
29    #[must_use]
30    pub fn checked_mul(&self, rhs: impl AsRef<UintRef>) -> CtOption<Self> {
31        let (res, overflow) = self.overflowing_mul(rhs.as_ref(), self.nlimbs());
32        CtOption::new(res, overflow.not())
33    }
34
35    /// Perform saturating multiplication, returning `MAX` on overflow.
36    #[must_use]
37    pub fn saturating_mul(&self, rhs: impl AsRef<UintRef>) -> Self {
38        let (mut res, overflow) = self.overflowing_mul(rhs.as_ref(), self.nlimbs());
39        res.as_mut_uint_ref().conditional_set_max(overflow);
40        res
41    }
42
43    /// Multiply `self` by `rhs`, wrapping to the width of `self`.
44    /// Returns a `Choice` indicating if the result overflowed the precision of `self`.
45    #[inline(always)]
46    #[must_use]
47    pub(crate) fn overflowing_mul(&self, rhs: &UintRef, size: usize) -> (Self, Choice) {
48        let mut limbs = vec![Limb::ZERO; size];
49        let overflow = self
50            .as_uint_ref()
51            .overflowing_mul(rhs, UintRef::new_mut(&mut limbs));
52        (limbs.into(), overflow)
53    }
54
55    /// Multiply `self` by `rhs`, wrapping to the width `size`.
56    /// Returns a pair of the wrapped product and a Limb representing the carry.
57    #[inline(always)]
58    fn wrapping_mul_carry(&self, rhs: &UintRef, size: usize) -> (Self, Limb) {
59        let mut limbs = vec![Limb::ZERO; size];
60        let carry = self
61            .as_uint_ref()
62            .wrapping_mul(rhs, UintRef::new_mut(limbs.as_mut_slice()));
63        (limbs.into(), carry)
64    }
65
66    /// Multiply `self` by itself.
67    #[must_use]
68    #[deprecated(since = "0.7.0", note = "please use `concatenating_square`")]
69    pub fn square(&self) -> Self {
70        self.concatenating_square()
71    }
72
73    /// Multiply `self` by itself, wrapping to the width of `self`.
74    #[must_use]
75    pub fn wrapping_square(&self) -> Self {
76        self.wrapping_square_carry(self.nlimbs()).0
77    }
78
79    /// Multiply `self` by itself, wrapping to the width of `self`.
80    /// Returns `CtOption::None` if the result overflowed the precision of `self`.
81    #[must_use]
82    pub fn checked_square(&self) -> CtOption<Self> {
83        let (res, overflow) = self.overflowing_square(self.nlimbs());
84        CtOption::new(res, overflow.not())
85    }
86
87    /// Perform saturating squaring, returning `MAX` on overflow.
88    #[must_use]
89    pub fn saturating_square(&self) -> Self {
90        let (mut res, overflow) = self.overflowing_square(self.nlimbs());
91        res.as_mut_uint_ref().conditional_set_max(overflow);
92        res
93    }
94
95    /// Multiply `self` by itself, wrapping to the width of `self`.
96    /// Returns a `Choice` indicating if the result overflowed the precision of `self`.
97    #[inline(always)]
98    #[must_use]
99    pub(crate) fn overflowing_square(&self, size: usize) -> (Self, Choice) {
100        let mut limbs = vec![Limb::ZERO; size];
101        let overflow = self
102            .as_uint_ref()
103            .overflowing_square(UintRef::new_mut(&mut limbs));
104        (limbs.into(), overflow)
105    }
106
107    /// Multiply `self` by itself, wrapping to the width `size`.
108    /// Returns a pair of the wrapped product and a Limb representing the carry.
109    #[inline(always)]
110    #[must_use]
111    fn wrapping_square_carry(&self, size: usize) -> (Self, Limb) {
112        let mut limbs = vec![Limb::ZERO; size];
113        let carry = self
114            .as_uint_ref()
115            .wrapping_square(UintRef::new_mut(limbs.as_mut_slice()));
116        (limbs.into(), carry)
117    }
118}
119
120impl<Rhs: AsRef<UintRef>> CheckedMul<Rhs> for BoxedUint {
121    fn checked_mul(&self, rhs: &Rhs) -> CtOption<Self> {
122        self.checked_mul(rhs)
123    }
124}
125
126impl<Rhs: AsRef<UintRef>> Mul<Rhs> for BoxedUint {
127    type Output = BoxedUint;
128
129    #[track_caller]
130    fn mul(self, rhs: Rhs) -> Self {
131        Mul::mul(&self, rhs)
132    }
133}
134
135impl<Rhs: AsRef<UintRef>> Mul<Rhs> for &BoxedUint {
136    type Output = BoxedUint;
137
138    #[track_caller]
139    fn mul(self, rhs: Rhs) -> Self::Output {
140        self.checked_mul(rhs)
141            .expect("attempted to multiply with overflow")
142    }
143}
144
145impl<Rhs: AsRef<UintRef>> MulAssign<Rhs> for BoxedUint {
146    fn mul_assign(&mut self, rhs: Rhs) {
147        *self = self
148            .checked_mul(rhs)
149            .expect("attempted to multiply with overflow");
150    }
151}
152
153impl<Rhs: AsRef<UintRef>> MulAssign<Rhs> for Wrapping<BoxedUint> {
154    fn mul_assign(&mut self, other: Rhs) {
155        self.0 = self.0.wrapping_mul(other);
156    }
157}
158
159impl<Rhs: AsRef<UintRef>> ConcatenatingMul<Rhs> for BoxedUint {
160    type Output = Self;
161
162    #[inline]
163    fn concatenating_mul(&self, rhs: Rhs) -> Self {
164        let rhs = rhs.as_ref();
165        self.wrapping_mul_carry(rhs, self.nlimbs() + rhs.nlimbs()).0
166    }
167}
168
169impl ConcatenatingSquare for BoxedUint {
170    type Output = Self;
171
172    #[inline]
173    fn concatenating_square(&self) -> Self {
174        self.wrapping_square_carry(self.nlimbs() * 2).0
175    }
176}
177
178impl WrappingMul for BoxedUint {
179    fn wrapping_mul(&self, v: &Self) -> Self {
180        self.wrapping_mul(v)
181    }
182}
183
184#[cfg(test)]
185mod tests {
186    use crate::{
187        BoxedUint, CheckedMul, ConcatenatingMul, ConcatenatingSquare, Limb, Resize, UintRef,
188        WrappingMul,
189    };
190
191    #[test]
192    fn mul_zero_and_one() {
193        assert!(bool::from(
194            BoxedUint::zero()
195                .concatenating_mul(BoxedUint::zero())
196                .is_zero()
197        ));
198        assert!(bool::from(
199            BoxedUint::zero()
200                .concatenating_mul(BoxedUint::one())
201                .is_zero()
202        ));
203        assert!(bool::from(
204            BoxedUint::one()
205                .concatenating_mul(BoxedUint::zero())
206                .is_zero()
207        ));
208        assert_eq!(
209            BoxedUint::one().concatenating_mul(BoxedUint::one()),
210            BoxedUint::one()
211        );
212        assert_eq!(BoxedUint::zero().concatenating_square(), BoxedUint::zero());
213        assert_eq!(BoxedUint::one().concatenating_square(), BoxedUint::one());
214    }
215
216    #[test]
217    fn mul_primes() {
218        let primes: &[u32] = &[3, 5, 17, 257, 65537];
219
220        for &a_int in primes {
221            for &b_int in primes {
222                let actual = BoxedUint::from(a_int).concatenating_mul(BoxedUint::from(b_int));
223                let expected = BoxedUint::from(u64::from(a_int) * u64::from(b_int));
224                assert_eq!(actual, expected);
225            }
226        }
227    }
228
229    #[test]
230    fn mul_trait() {
231        let expect = BoxedUint::one() * BoxedUint::from(2u8);
232        assert_eq!(expect, BoxedUint::one() * &BoxedUint::from(2u8));
233    }
234
235    #[should_panic]
236    #[test]
237    fn mul_trait_panic() {
238        let _ = BoxedUint::max(64) * BoxedUint::max(64);
239    }
240
241    #[cfg(feature = "rand_core")]
242    #[test]
243    fn mul_cmp() {
244        use crate::{RandomBits, Resize};
245        use rand_core::SeedableRng;
246        let mut rng = chacha20::ChaCha8Rng::seed_from_u64(1);
247        let bits = if cfg!(miri) { 512 } else { 4096 };
248        let rounds = if cfg!(miri) { 10 } else { 50 };
249
250        for i in 0..rounds {
251            let a = BoxedUint::random_bits(&mut rng, bits);
252            assert_eq!(
253                a.concatenating_mul(&a),
254                a.concatenating_square(),
255                "a={a}, i={i}"
256            );
257            assert_eq!(a.wrapping_mul(&a), a.wrapping_square(), "a={a}, i={i}");
258            assert_eq!(a.saturating_mul(&a), a.saturating_square(), "a={a}, i={i}");
259        }
260
261        for i in 0..rounds {
262            let a = BoxedUint::random_bits(&mut rng, bits);
263            let b = BoxedUint::random_bits(&mut rng, bits + 64);
264            let expect = a.concatenating_mul(&b);
265            assert_eq!(
266                ConcatenatingMul::concatenating_mul(&b, &a),
267                expect,
268                "a={a}, b={b}, i={i}"
269            );
270            assert_eq!(
271                WrappingMul::wrapping_mul(&a, &b),
272                expect.clone().resize_unchecked(a.bits_precision()),
273                "a={a}, b={b}, i={i}"
274            );
275            assert_eq!(
276                WrappingMul::wrapping_mul(&b, &a),
277                expect.clone().resize_unchecked(b.bits_precision()),
278                "a={a}, b={b}, i={i}"
279            );
280        }
281    }
282
283    #[test]
284    fn checked_mul_cmp() {
285        let n = BoxedUint::max(64)
286            .resize_unchecked(256)
287            .wrapping_add(BoxedUint::one());
288        let n2 = n.checked_square();
289        assert!(n2.is_some().to_bool());
290        let n2_c = CheckedMul::checked_mul(&n, &n);
291        assert_eq!(n2.clone().into_option(), n2_c.into_option());
292        let n2 = n2.unwrap();
293
294        let n4 = n2.checked_square();
295        assert!(n4.is_none().to_bool());
296        let n4_c = CheckedMul::checked_mul(&n2, &n2);
297        assert!(n4_c.is_none().to_bool());
298
299        let z = BoxedUint::zero_with_precision(256);
300        let z2 = z.checked_square();
301        assert!(z2.is_some().to_bool());
302        let z2_c = CheckedMul::checked_mul(&z, &z);
303        assert_eq!(z2.into_option(), z2_c.into_option());
304
305        let m = BoxedUint::max(256);
306        assert!(m.checked_square().is_none().to_bool());
307        assert!(CheckedMul::checked_mul(&m, &m).is_none().to_bool());
308    }
309
310    #[test]
311    fn mul_uintref() {
312        let a = BoxedUint::from(1234567890u64);
313        let b = UintRef::new(&[Limb(456), Limb(0)]);
314        assert_eq!(a * b, BoxedUint::from(562962957840u64));
315    }
316}
crypto_bigint/uint/boxed/mul.rs

crypto_bigint/uint/boxed/
mul.rs
