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

crypto_bigint/uint/
mul.rs
