crypto_bigint/uint/
lcm.rs

1//! This module implements Least common multiple (LCM) for [`Uint`].
2
3use crate::{Concat, NonZero, Uint};
4
5impl<const LIMBS: usize> Uint<LIMBS> {
6    /// Compute the least common multiple of `self` and `rhs`.
7    #[must_use]
8    pub const fn lcm<const WIDE_LIMBS: usize>(&self, rhs: &Self) -> Uint<WIDE_LIMBS>
9    where
10        Self: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
11    {
12        let self_is_nz = self.is_nonzero();
13        let rhs_is_nz = rhs.is_nonzero();
14
15        let gcd_nz = NonZero(self.gcd(&Uint::select(&Uint::ONE, rhs, rhs_is_nz)));
16
17        let lcm = self.wrapping_div(&gcd_nz).concatenating_mul(rhs);
18
19        Uint::select(&Uint::ZERO, &lcm, self_is_nz.and(rhs_is_nz))
20    }
21}
22
23#[cfg(test)]
24mod tests {
25    mod lcm {
26        use crate::{Concat, U64, U128, U256, U512, U1024, U2048, U4096, U8192, Uint};
27
28        fn test<const LIMBS: usize, const WIDE_LIMBS: usize>(
29            lhs: Uint<LIMBS>,
30            rhs: Uint<LIMBS>,
31            target: Uint<WIDE_LIMBS>,
32        ) where
33            Uint<LIMBS>: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
34        {
35            assert_eq!(lhs.lcm(&rhs), target);
36        }
37
38        fn run_tests<const LIMBS: usize, const WIDE_LIMBS: usize>()
39        where
40            Uint<LIMBS>: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
41        {
42            test(Uint::<LIMBS>::ZERO, Uint::ZERO, Uint::<WIDE_LIMBS>::ZERO);
43            test(Uint::<LIMBS>::ZERO, Uint::ONE, Uint::<WIDE_LIMBS>::ZERO);
44            test(Uint::<LIMBS>::ZERO, Uint::MAX, Uint::<WIDE_LIMBS>::ZERO);
45            test(Uint::<LIMBS>::ONE, Uint::ZERO, Uint::<WIDE_LIMBS>::ZERO);
46            test(Uint::<LIMBS>::ONE, Uint::ONE, Uint::<WIDE_LIMBS>::ONE);
47            test(
48                Uint::<LIMBS>::ONE,
49                Uint::MAX,
50                Uint::<LIMBS>::MAX.resize::<WIDE_LIMBS>(),
51            );
52            test(Uint::<LIMBS>::MAX, Uint::ZERO, Uint::<WIDE_LIMBS>::ZERO);
53            test(
54                Uint::<LIMBS>::MAX,
55                Uint::ONE,
56                Uint::<LIMBS>::MAX.resize::<WIDE_LIMBS>(),
57            );
58            test(
59                Uint::<LIMBS>::MAX,
60                Uint::MAX,
61                Uint::<LIMBS>::MAX.resize::<WIDE_LIMBS>(),
62            );
63        }
64
65        #[test]
66        fn lcm_sizes() {
67            run_tests::<{ U64::LIMBS }, { U128::LIMBS }>();
68            run_tests::<{ U128::LIMBS }, { U256::LIMBS }>();
69            run_tests::<{ U256::LIMBS }, { U512::LIMBS }>();
70            run_tests::<{ U512::LIMBS }, { U1024::LIMBS }>();
71            if cfg!(not(miri)) {
72                run_tests::<{ U1024::LIMBS }, { U2048::LIMBS }>();
73                run_tests::<{ U2048::LIMBS }, { U4096::LIMBS }>();
74                run_tests::<{ U4096::LIMBS }, { U8192::LIMBS }>();
75            }
76        }
77    }
78}
crypto_bigint/uint/lcm.rs

crypto_bigint/uint/
lcm.rs
