crypto_bigint/uint/
lcm.rs

1//! This module implements Least common multiple (LCM) for [`Uint`].
2
3use crate::{Concat, Lcm, 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 (lhs_nz, _) = self.to_nz_or_one();
13        let gcd_nz = lhs_nz.gcd_unsigned(rhs);
14        self.div_exact(&gcd_nz)
15            .expect_copied("invalid gcd")
16            .concatenating_mul(rhs)
17    }
18
19    /// Compute the least common multiple of `self` and `rhs`.
20    ///
21    /// This method is variable time with respect to `self` and `rhs`.
22    #[must_use]
23    pub const fn lcm_vartime<const WIDE_LIMBS: usize>(&self, rhs: &Self) -> Uint<WIDE_LIMBS>
24    where
25        Self: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
26    {
27        let (Some(lhs_nz), false) = (self.as_nz_vartime(), rhs.is_zero_vartime()) else {
28            return Uint::ZERO;
29        };
30        let gcd_nz = lhs_nz.gcd_unsigned_vartime(rhs);
31        self.div_exact_vartime(&gcd_nz)
32            .expect_copied("invalid gcd")
33            .concatenating_mul(rhs)
34    }
35}
36
37impl<const LIMBS: usize, const WIDE_LIMBS: usize> Lcm for Uint<LIMBS>
38where
39    Self: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
40{
41    type Output = Uint<WIDE_LIMBS>;
42
43    fn lcm(&self, rhs: &Self) -> Self::Output {
44        self.lcm(rhs)
45    }
46
47    fn lcm_vartime(&self, rhs: &Self) -> Self::Output {
48        self.lcm_vartime(rhs)
49    }
50}
51
52#[cfg(test)]
53mod tests {
54    mod lcm {
55        use crate::{Concat, Lcm, U64, U128, U512, U1024, U4096, U8192, Uint};
56
57        fn test<const LIMBS: usize, const WIDE_LIMBS: usize>(
58            lhs: Uint<LIMBS>,
59            rhs: Uint<LIMBS>,
60            target: Uint<WIDE_LIMBS>,
61        ) where
62            Uint<LIMBS>: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
63        {
64            assert_eq!(lhs.lcm(&rhs), target);
65            assert_eq!(lhs.lcm_vartime(&rhs), target);
66            assert_eq!(Lcm::lcm(&lhs, &rhs), target);
67            assert_eq!(Lcm::lcm_vartime(&lhs, &rhs), target);
68        }
69
70        fn run_tests<const LIMBS: usize, const WIDE_LIMBS: usize>()
71        where
72            Uint<LIMBS>: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
73        {
74            test(Uint::<LIMBS>::ZERO, Uint::ZERO, Uint::<WIDE_LIMBS>::ZERO);
75            test(Uint::<LIMBS>::ZERO, Uint::ONE, Uint::<WIDE_LIMBS>::ZERO);
76            test(Uint::<LIMBS>::ZERO, Uint::MAX, Uint::<WIDE_LIMBS>::ZERO);
77            test(Uint::<LIMBS>::ONE, Uint::ZERO, Uint::<WIDE_LIMBS>::ZERO);
78            test(Uint::<LIMBS>::ONE, Uint::ONE, Uint::<WIDE_LIMBS>::ONE);
79            test(
80                Uint::<LIMBS>::ONE,
81                Uint::MAX,
82                Uint::<LIMBS>::MAX.resize::<WIDE_LIMBS>(),
83            );
84            test(Uint::<LIMBS>::MAX, Uint::ZERO, Uint::<WIDE_LIMBS>::ZERO);
85            test(
86                Uint::<LIMBS>::MAX,
87                Uint::ONE,
88                Uint::<LIMBS>::MAX.resize::<WIDE_LIMBS>(),
89            );
90            test(
91                Uint::<LIMBS>::MAX,
92                Uint::MAX,
93                Uint::<LIMBS>::MAX.resize::<WIDE_LIMBS>(),
94            );
95        }
96
97        #[test]
98        fn lcm_sizes() {
99            run_tests::<{ U64::LIMBS }, { U128::LIMBS }>();
100            run_tests::<{ U512::LIMBS }, { U1024::LIMBS }>();
101            if cfg!(not(miri)) {
102                run_tests::<{ U4096::LIMBS }, { U8192::LIMBS }>();
103            }
104        }
105    }
106}
crypto_bigint/uint/lcm.rs

crypto_bigint/uint/
lcm.rs
