crypto_bigint/uint/
mul.rs

1//! [`Uint`] multiplication operations.
2
3use crate::{
4    Checked, CheckedMul, Choice, Concat, ConcatenatingMul, ConcatenatingSquare, CtOption, Limb,
5    Mul, MulAssign, Uint, Wrapping, WrappingMul,
6};
7
8pub(crate) mod karatsuba;
9pub(crate) mod schoolbook;
10
11impl<const LIMBS: usize> Uint<LIMBS> {
12    /// Multiply `self` by `rhs`, returning a concatenated "wide" result.
13    #[inline]
14    #[must_use]
15    pub const fn concatenating_mul<const RHS_LIMBS: usize, const WIDE_LIMBS: usize>(
16        &self,
17        rhs: &Uint<RHS_LIMBS>,
18    ) -> Uint<WIDE_LIMBS>
19    where
20        Self: Concat<RHS_LIMBS, Output = Uint<WIDE_LIMBS>>,
21    {
22        let (lo, hi) = self.widening_mul(rhs);
23        Uint::concat_mixed(&lo, &hi)
24    }
25
26    /// Compute "wide" multiplication as a 2-tuple containing the `(lo, hi)` components of the product, whose sizes
27    /// correspond to the sizes of the operands.
28    #[deprecated(since = "0.7.0", note = "please use `widening_mul` instead")]
29    #[must_use]
30    pub const fn split_mul<const RHS_LIMBS: usize>(
31        &self,
32        rhs: &Uint<RHS_LIMBS>,
33    ) -> (Self, Uint<RHS_LIMBS>) {
34        self.widening_mul(rhs)
35    }
36
37    /// Compute "wide" multiplication as a 2-tuple containing the `(lo, hi)` components of the product, whose sizes
38    /// correspond to the sizes of the operands.
39    #[inline(always)]
40    #[must_use]
41    pub const fn widening_mul<const RHS_LIMBS: usize>(
42        &self,
43        rhs: &Uint<RHS_LIMBS>,
44    ) -> (Self, Uint<RHS_LIMBS>) {
45        karatsuba::widening_mul_fixed(self.as_uint_ref(), rhs.as_uint_ref())
46    }
47
48    /// Perform wrapping multiplication, discarding overflow.
49    #[inline]
50    #[must_use]
51    pub const fn wrapping_mul<const RHS_LIMBS: usize>(&self, rhs: &Uint<RHS_LIMBS>) -> Self {
52        karatsuba::wrapping_mul_fixed::<LIMBS>(self.as_uint_ref(), rhs.as_uint_ref()).0
53    }
54
55    /// Perform saturating multiplication, returning `MAX` on overflow.
56    #[must_use]
57    pub const fn saturating_mul<const RHS_LIMBS: usize>(&self, rhs: &Uint<RHS_LIMBS>) -> Self {
58        let (lo, overflow) = self.overflowing_mul(rhs);
59        Self::select(&lo, &Self::MAX, overflow)
60    }
61
62    /// Perform wrapping multiplication, checking that the result fits in the original [`Uint`] size.
63    #[must_use]
64    pub const fn checked_mul<const RHS_LIMBS: usize>(
65        &self,
66        rhs: &Uint<RHS_LIMBS>,
67    ) -> CtOption<Uint<LIMBS>> {
68        let (lo, overflow) = self.overflowing_mul(rhs);
69        CtOption::new(lo, overflow.not())
70    }
71
72    /// Perform overflowing multiplication, returning the wrapped result and a `Choice`
73    /// indicating whether overflow occurred.
74    #[inline(always)]
75    #[must_use]
76    pub(crate) const fn overflowing_mul<const RHS_LIMBS: usize>(
77        &self,
78        rhs: &Uint<RHS_LIMBS>,
79    ) -> (Uint<LIMBS>, Choice) {
80        let (lo, carry) = karatsuba::wrapping_mul_fixed(self.as_uint_ref(), rhs.as_uint_ref());
81        let overflow = self
82            .as_uint_ref()
83            .check_mul_overflow(rhs.as_uint_ref(), carry.is_nonzero());
84        (lo, overflow)
85    }
86
87    /// Perform multiplication by a Limb, returning the wrapped result and a Limb overflow.
88    #[inline]
89    pub(crate) const fn overflowing_mul_limb(&self, rhs: Limb) -> (Self, Limb) {
90        let mut ret = [Limb::ZERO; LIMBS];
91        let mut i = 0;
92        let mut carry = Limb::ZERO;
93        while i < LIMBS {
94            (ret[i], carry) = self.limbs[i].carrying_mul_add(rhs, Limb::ZERO, carry);
95            i += 1;
96        }
97        (Uint::new(ret), carry)
98    }
99
100    /// Perform wrapping multiplication by a Limb, discarding overflow.
101    #[inline]
102    pub(crate) const fn wrapping_mul_limb(&self, rhs: Limb) -> Self {
103        self.overflowing_mul_limb(rhs).0
104    }
105}
106
107/// Squaring operations
108impl<const LIMBS: usize> Uint<LIMBS> {
109    /// Square self, returning a "wide" result in two parts as (lo, hi).
110    #[inline(always)]
111    #[must_use]
112    #[deprecated(since = "0.7.0", note = "please use `widening_square` instead")]
113    pub const fn square_wide(&self) -> (Self, Self) {
114        self.widening_square()
115    }
116
117    /// Square self, returning a "wide" result in two parts as `(lo, hi)`.
118    #[inline(always)]
119    #[must_use]
120    pub const fn widening_square(&self) -> (Self, Self) {
121        karatsuba::widening_square_fixed(self.as_uint_ref())
122    }
123
124    /// Square self, returning a concatenated "wide" result.
125    #[inline]
126    #[must_use]
127    pub const fn concatenating_square<const WIDE_LIMBS: usize>(&self) -> Uint<WIDE_LIMBS>
128    where
129        Self: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
130    {
131        let (lo, hi) = self.widening_square();
132        Uint::concat_mixed(&lo, &hi)
133    }
134
135    /// Square self, checking that the result fits in the original [`Uint`] size.
136    #[must_use]
137    pub const fn checked_square(&self) -> CtOption<Uint<LIMBS>> {
138        let (lo, overflow) = self.overflowing_square();
139        CtOption::new(lo, overflow.not())
140    }
141
142    /// Perform wrapping square, discarding overflow.
143    #[inline]
144    #[must_use]
145    pub const fn wrapping_square(&self) -> Uint<LIMBS> {
146        karatsuba::wrapping_square_fixed(self.as_uint_ref()).0
147    }
148
149    /// Perform saturating squaring, returning `MAX` on overflow.
150    #[must_use]
151    pub const fn saturating_square(&self) -> Self {
152        let (lo, overflow) = self.overflowing_square();
153        Self::select(&lo, &Self::MAX, overflow)
154    }
155
156    /// Perform overflowing squaring, returning the wrapped result and a `Choice`
157    /// indicating whether overflow occurred.
158    #[inline(always)]
159    #[must_use]
160    pub(crate) const fn overflowing_square(&self) -> (Uint<LIMBS>, Choice) {
161        let (lo, carry) = karatsuba::wrapping_square_fixed(self.as_uint_ref());
162        let overflow = self.as_uint_ref().check_square_overflow(carry.is_nonzero());
163        (lo, overflow)
164    }
165}
166
167impl<const LIMBS: usize, const WIDE_LIMBS: usize> Uint<LIMBS>
168where
169    Self: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
170{
171    /// Square self, returning a concatenated "wide" result.
172    #[must_use]
173    #[deprecated(since = "0.7.0", note = "please use `concatenating_square` instead")]
174    pub const fn square(&self) -> Uint<WIDE_LIMBS> {
175        let (lo, hi) = self.widening_square();
176        lo.concat(&hi)
177    }
178}
179
180impl<const LIMBS: usize, const RHS_LIMBS: usize> CheckedMul<Uint<RHS_LIMBS>> for Uint<LIMBS> {
181    fn checked_mul(&self, rhs: &Uint<RHS_LIMBS>) -> CtOption<Self> {
182        self.checked_mul(rhs)
183    }
184}
185
186impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<Uint<RHS_LIMBS>> for Uint<LIMBS> {
187    type Output = Uint<LIMBS>;
188
189    fn mul(self, rhs: Uint<RHS_LIMBS>) -> Self {
190        self.mul(&rhs)
191    }
192}
193
194impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<&Uint<RHS_LIMBS>> for Uint<LIMBS> {
195    type Output = Uint<LIMBS>;
196
197    fn mul(self, rhs: &Uint<RHS_LIMBS>) -> Self {
198        (&self).mul(rhs)
199    }
200}
201
202impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<Uint<RHS_LIMBS>> for &Uint<LIMBS> {
203    type Output = Uint<LIMBS>;
204
205    fn mul(self, rhs: Uint<RHS_LIMBS>) -> Self::Output {
206        self.mul(&rhs)
207    }
208}
209
210impl<const LIMBS: usize, const RHS_LIMBS: usize> Mul<&Uint<RHS_LIMBS>> for &Uint<LIMBS> {
211    type Output = Uint<LIMBS>;
212
213    fn mul(self, rhs: &Uint<RHS_LIMBS>) -> Self::Output {
214        self.checked_mul(rhs)
215            .expect("attempted to multiply with overflow")
216    }
217}
218
219impl<const LIMBS: usize, const RHS_LIMBS: usize> MulAssign<Uint<RHS_LIMBS>> for Uint<LIMBS> {
220    fn mul_assign(&mut self, rhs: Uint<RHS_LIMBS>) {
221        *self = self.mul(&rhs);
222    }
223}
224
225impl<const LIMBS: usize, const RHS_LIMBS: usize> MulAssign<&Uint<RHS_LIMBS>> for Uint<LIMBS> {
226    fn mul_assign(&mut self, rhs: &Uint<RHS_LIMBS>) {
227        *self = self.mul(rhs);
228    }
229}
230
231impl<const LIMBS: usize> MulAssign<Wrapping<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
232    fn mul_assign(&mut self, other: Wrapping<Uint<LIMBS>>) {
233        *self = *self * other;
234    }
235}
236
237impl<const LIMBS: usize> MulAssign<&Wrapping<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
238    fn mul_assign(&mut self, other: &Wrapping<Uint<LIMBS>>) {
239        *self = *self * other;
240    }
241}
242
243impl<const LIMBS: usize> MulAssign<Checked<Uint<LIMBS>>> for Checked<Uint<LIMBS>> {
244    fn mul_assign(&mut self, other: Checked<Uint<LIMBS>>) {
245        *self = *self * other;
246    }
247}
248
249impl<const LIMBS: usize> MulAssign<&Checked<Uint<LIMBS>>> for Checked<Uint<LIMBS>> {
250    fn mul_assign(&mut self, other: &Checked<Uint<LIMBS>>) {
251        *self = *self * other;
252    }
253}
254
255impl<const LIMBS: usize, const RHS_LIMBS: usize, const WIDE_LIMBS: usize>
256    ConcatenatingMul<Uint<RHS_LIMBS>> for Uint<LIMBS>
257where
258    Self: Concat<RHS_LIMBS, Output = Uint<WIDE_LIMBS>>,
259{
260    type Output = Uint<WIDE_LIMBS>;
261
262    #[inline]
263    fn concatenating_mul(&self, rhs: Uint<RHS_LIMBS>) -> Self::Output {
264        self.concatenating_mul(&rhs)
265    }
266}
267
268impl<const LIMBS: usize, const RHS_LIMBS: usize, const WIDE_LIMBS: usize>
269    ConcatenatingMul<&Uint<RHS_LIMBS>> for Uint<LIMBS>
270where
271    Self: Concat<RHS_LIMBS, Output = Uint<WIDE_LIMBS>>,
272{
273    type Output = Uint<WIDE_LIMBS>;
274
275    #[inline]
276    fn concatenating_mul(&self, rhs: &Uint<RHS_LIMBS>) -> Self::Output {
277        self.concatenating_mul(rhs)
278    }
279}
280
281impl<const LIMBS: usize, const WIDE_LIMBS: usize> ConcatenatingSquare for Uint<LIMBS>
282where
283    Self: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
284{
285    type Output = Uint<WIDE_LIMBS>;
286
287    #[inline]
288    fn concatenating_square(&self) -> Self::Output {
289        self.concatenating_square()
290    }
291}
292
293impl<const LIMBS: usize> WrappingMul for Uint<LIMBS> {
294    fn wrapping_mul(&self, v: &Self) -> Self {
295        self.wrapping_mul(v)
296    }
297}
298
299#[cfg(test)]
300mod tests {
301    use crate::{ConcatenatingMul, ConcatenatingSquare, Limb, U64, U128, U192, U256, Uint};
302
303    #[test]
304    fn widening_mul_zero_and_one() {
305        assert_eq!(U64::ZERO.widening_mul(&U64::ZERO), (U64::ZERO, U64::ZERO));
306        assert_eq!(U64::ZERO.widening_mul(&U64::ONE), (U64::ZERO, U64::ZERO));
307        assert_eq!(U64::ONE.widening_mul(&U64::ZERO), (U64::ZERO, U64::ZERO));
308        assert_eq!(U64::ONE.widening_mul(&U64::ONE), (U64::ONE, U64::ZERO));
309    }
310
311    #[test]
312    fn widening_mul_lo_only() {
313        let primes: &[u32] = &[3, 5, 17, 257, 65537];
314
315        for &a_int in primes {
316            for &b_int in primes {
317                let (lo, hi) = U64::from_u32(a_int).widening_mul(&U64::from_u32(b_int));
318                let expected = U64::from_u64(u64::from(a_int) * u64::from(b_int));
319                assert_eq!(lo, expected);
320                assert!(bool::from(hi.is_zero()));
321                assert_eq!(lo, U64::from_u32(a_int).wrapping_mul(&U64::from_u32(b_int)));
322            }
323        }
324    }
325
326    #[test]
327    fn mul_concat_even() {
328        assert_eq!(U64::ZERO.concatenating_mul(&U64::MAX), U128::ZERO);
329        assert_eq!(U64::MAX.concatenating_mul(&U64::ZERO), U128::ZERO);
330        assert_eq!(
331            U64::MAX.concatenating_mul(&U64::MAX),
332            U128::from_u128(0xfffffffffffffffe_0000000000000001)
333        );
334        assert_eq!(
335            U64::ONE.concatenating_mul(&U64::MAX),
336            U128::from_u128(0x0000000000000000_ffffffffffffffff)
337        );
338    }
339
340    #[test]
341    fn mul_concat_mixed() {
342        let a = U64::from_u64(0x0011223344556677);
343        let b = U128::from_u128(0x8899aabbccddeeff_8899aabbccddeeff);
344        let expected = U192::from(&b).saturating_mul(&a);
345        assert_eq!(a.concatenating_mul(&b), expected);
346        assert_eq!(ConcatenatingMul::concatenating_mul(&a, &b), expected);
347        assert_eq!(b.concatenating_mul(&a), expected);
348        assert_eq!(ConcatenatingMul::concatenating_mul(&b, &a), expected);
349    }
350
351    #[test]
352    fn wrapping_mul_even() {
353        assert_eq!(U64::ZERO.wrapping_mul(&U64::MAX), U64::ZERO);
354        assert_eq!(U64::MAX.wrapping_mul(&U64::ZERO), U64::ZERO);
355        assert_eq!(U64::MAX.wrapping_mul(&U64::MAX), U64::ONE);
356        assert_eq!(U64::ONE.wrapping_mul(&U64::MAX), U64::MAX);
357    }
358
359    #[test]
360    fn wrapping_mul_mixed() {
361        let a = U64::from_u64(0x0011223344556677);
362        let b = U128::from_u128(0x8899aabbccddeeff_8899aabbccddeeff);
363        let expected = U192::from(&b).saturating_mul(&a);
364        assert_eq!(b.wrapping_mul(&a), expected.resize());
365        assert_eq!(a.wrapping_mul(&b), expected.resize());
366    }
367
368    #[test]
369    fn checked_mul_ok() {
370        let n = U64::from_u32(0xffff_ffff);
371        assert_eq!(
372            n.checked_mul(&n).unwrap(),
373            U64::from_u64(0xffff_fffe_0000_0001)
374        );
375        assert_eq!(U64::ZERO.checked_mul(&U64::ZERO).unwrap(), U64::ZERO);
376    }
377
378    #[test]
379    fn checked_mul_overflow() {
380        let n = U64::MAX;
381        assert!(bool::from(n.checked_mul(&n).is_none()));
382    }
383
384    #[test]
385    fn saturating_mul_no_overflow() {
386        let n = U64::from_u8(8);
387        assert_eq!(n.saturating_mul(&n), U64::from_u8(64));
388    }
389
390    #[test]
391    fn saturating_mul_overflow() {
392        let a = U64::from(0xffff_ffff_ffff_ffffu64);
393        let b = U64::from(2u8);
394        assert_eq!(a.saturating_mul(&b), U64::MAX);
395    }
396
397    #[test]
398    fn concatenating_square() {
399        let n = U64::from_u64(0xffff_ffff_ffff_ffff);
400        let (lo, hi) = n.concatenating_square().split();
401        assert_eq!(lo, U64::from_u64(1));
402        assert_eq!(hi, U64::from_u64(0xffff_ffff_ffff_fffe));
403        let check = ConcatenatingSquare::concatenating_square(&n).split();
404        assert_eq!(check, (lo, hi));
405    }
406
407    #[test]
408    fn concatenating_square_larger() {
409        let n = U256::MAX;
410        let (lo, hi) = n.concatenating_square().split();
411        assert_eq!(lo, U256::ONE);
412        assert_eq!(hi, U256::MAX.wrapping_sub(&U256::ONE));
413    }
414
415    #[test]
416    fn checked_square() {
417        let n = U256::from_u64(u64::MAX).wrapping_add(&U256::ONE);
418        let n2 = n.checked_square();
419        assert!(n2.is_some().to_bool());
420        let n4 = n2.unwrap().checked_square();
421        assert!(n4.is_none().to_bool());
422        let z = U256::ZERO.checked_square();
423        assert!(z.is_some().to_bool());
424        let m = U256::MAX.checked_square();
425        assert!(m.is_none().to_bool());
426    }
427
428    #[test]
429    fn wrapping_square() {
430        let n = U256::from_u64(u64::MAX).wrapping_add(&U256::ONE);
431        let n2 = n.wrapping_square();
432        assert_eq!(n2, U256::from_u128(u128::MAX).wrapping_add(&U256::ONE));
433        let n4 = n2.wrapping_square();
434        assert_eq!(n4, U256::ZERO);
435    }
436
437    #[test]
438    fn saturating_square() {
439        let n = U256::from_u64(u64::MAX).wrapping_add(&U256::ONE);
440        let n2 = n.saturating_square();
441        assert_eq!(n2, U256::from_u128(u128::MAX).wrapping_add(&U256::ONE));
442        let n4 = n2.saturating_square();
443        assert_eq!(n4, U256::MAX);
444    }
445
446    #[cfg(feature = "rand_core")]
447    #[test]
448    fn mul_cmp() {
449        use crate::{Random, U4096};
450        use rand_core::SeedableRng;
451        let mut rng = chacha20::ChaCha8Rng::seed_from_u64(1);
452
453        let rounds = if cfg!(miri) { 10 } else { 50 };
454        for _ in 0..rounds {
455            let a = U4096::random_from_rng(&mut rng);
456            assert_eq!(a.concatenating_mul(&a), a.concatenating_square(), "a = {a}");
457            assert_eq!(a.widening_mul(&a), a.widening_square(), "a = {a}");
458            assert_eq!(a.wrapping_mul(&a), a.wrapping_square(), "a = {a}");
459            assert_eq!(a.saturating_mul(&a), a.saturating_square(), "a = {a}");
460        }
461    }
462
463    #[test]
464    fn checked_mul_sizes() {
465        const SIZE_A: usize = 4;
466        const SIZE_B: usize = 8;
467
468        for n in 0..Uint::<SIZE_A>::BITS {
469            let mut a = Uint::<SIZE_A>::ZERO;
470            a = a.set_bit_vartime(n, true);
471
472            for m in (0..Uint::<SIZE_B>::BITS).step_by(16) {
473                let mut b = Uint::<SIZE_B>::ZERO;
474                b = b.set_bit_vartime(m, true);
475                let res = a.widening_mul(&b);
476                let res_overflow = res.1.is_nonzero();
477                let checked = a.checked_mul(&b);
478                assert_eq!(checked.is_some().to_bool(), res_overflow.not().to_bool());
479                assert_eq!(
480                    checked.as_inner_unchecked(),
481                    &res.0,
482                    "a = 2**{n}, b = 2**{m}"
483                );
484            }
485        }
486    }
487
488    #[test]
489    fn checked_square_sizes() {
490        const SIZE: usize = 4;
491
492        for n in 0..Uint::<SIZE>::BITS {
493            let mut a = Uint::<SIZE>::ZERO;
494            a = a.set_bit_vartime(n, true);
495
496            let res = a.widening_square();
497            let res_overflow = res.1.is_nonzero();
498            let checked = a.checked_square();
499            assert_eq!(checked.is_some().to_bool(), res_overflow.not().to_bool());
500            assert_eq!(checked.as_inner_unchecked(), &res.0, "a = 2**{n}");
501        }
502    }
503
504    #[test]
505    fn overflowing_mul_limb() {
506        let (max_lo, max_hi) = U128::MAX.widening_mul(&U128::from(Limb::MAX));
507
508        let result = U128::ZERO.overflowing_mul_limb(Limb::ZERO);
509        assert_eq!(result, (U128::ZERO, Limb::ZERO));
510        let result = U128::ZERO.overflowing_mul_limb(Limb::ONE);
511        assert_eq!(result, (U128::ZERO, Limb::ZERO));
512        let result = U128::MAX.overflowing_mul_limb(Limb::ZERO);
513        assert_eq!(result, (U128::ZERO, Limb::ZERO));
514        let result = U128::MAX.overflowing_mul_limb(Limb::ONE);
515        assert_eq!(result, (U128::MAX, Limb::ZERO));
516        let result = U128::MAX.overflowing_mul_limb(Limb::MAX);
517        assert_eq!(result, (max_lo, max_hi.limbs[0]));
518
519        assert_eq!(U128::ZERO.wrapping_mul_limb(Limb::ZERO), U128::ZERO);
520        assert_eq!(U128::ZERO.wrapping_mul_limb(Limb::ONE), U128::ZERO);
521        assert_eq!(U128::MAX.wrapping_mul_limb(Limb::ZERO), U128::ZERO);
522        assert_eq!(U128::MAX.wrapping_mul_limb(Limb::ONE), U128::MAX);
523        assert_eq!(U128::MAX.wrapping_mul_limb(Limb::MAX), max_lo);
524    }
525}
crypto_bigint/uint/mul.rs

crypto_bigint/uint/
mul.rs
