crypto_bigint/uint/boxed/
lcm.rs

1//! This module implements Least common multiple (LCM) for [`BoxedUint`].
2
3use crate::{BoxedUint, ConcatenatingMul, Gcd, Lcm};
4
5impl Lcm for BoxedUint {
6    type Output = Self;
7
8    fn lcm(&self, rhs: &Self) -> Self {
9        let (lhs_nz, _) = self.to_nz_or_one();
10        let gcd_nz = lhs_nz.gcd(rhs);
11        self.div_exact(&gcd_nz)
12            .expect("invalid gcd")
13            .concatenating_mul(rhs)
14    }
15
16    fn lcm_vartime(&self, rhs: &Self) -> Self {
17        let (Some(lhs_nz), false) = (self.as_nz_vartime(), rhs.is_zero_vartime()) else {
18            return BoxedUint::zero_with_precision(self.bits_precision() + rhs.bits_precision());
19        };
20        let gcd_nz = lhs_nz.gcd_vartime(rhs);
21        self.div_exact_vartime(&gcd_nz)
22            .expect("invalid gcd")
23            .concatenating_mul(rhs)
24    }
25}
26
27#[cfg(test)]
28mod tests {
29    mod lcm {
30        use crate::{BoxedUint, Lcm};
31
32        fn test(lhs: &BoxedUint, rhs: &BoxedUint, target: &BoxedUint) {
33            assert_eq!(lhs.lcm(rhs), target);
34            assert_eq!(lhs.lcm_vartime(rhs), target);
35        }
36
37        #[test]
38        fn lcm_sizes() {
39            let sizes = [128, 256];
40            for size in sizes {
41                test(
42                    &BoxedUint::zero_with_precision(size),
43                    &BoxedUint::zero_with_precision(size),
44                    &BoxedUint::zero(),
45                );
46                test(
47                    &BoxedUint::zero_with_precision(size),
48                    &BoxedUint::one_with_precision(size),
49                    &BoxedUint::zero(),
50                );
51                test(
52                    &BoxedUint::zero_with_precision(size),
53                    &BoxedUint::max(size),
54                    &BoxedUint::zero(),
55                );
56                test(
57                    &BoxedUint::one_with_precision(size),
58                    &BoxedUint::zero_with_precision(size),
59                    &BoxedUint::zero(),
60                );
61                test(
62                    &BoxedUint::one_with_precision(size),
63                    &BoxedUint::one_with_precision(size),
64                    &BoxedUint::one(),
65                );
66                test(
67                    &BoxedUint::one_with_precision(size),
68                    &BoxedUint::max(size),
69                    &BoxedUint::max(size),
70                );
71                test(
72                    &BoxedUint::max(size),
73                    &BoxedUint::zero_with_precision(size),
74                    &BoxedUint::zero(),
75                );
76                test(
77                    &BoxedUint::max(size),
78                    &BoxedUint::one_with_precision(size),
79                    &BoxedUint::max(size),
80                );
81                test(
82                    &BoxedUint::max(size),
83                    &BoxedUint::max(size),
84                    &BoxedUint::max(size),
85                );
86            }
87        }
88    }
89}
crypto_bigint/uint/boxed/lcm.rs

crypto_bigint/uint/boxed/
lcm.rs
