crypto_bigint/uint/boxed/
gcd.rs

1//! Support for computing greatest common divisor of two `BoxedUint`s.
2
3use super::BoxedUint;
4use crate::{Gcd, NonZero, Odd, modular::safegcd};
5
6impl Gcd for BoxedUint {
7    type Output = Self;
8
9    /// Compute the greatest common divisor (GCD) of this number and another.
10    fn gcd(&self, rhs: &Self) -> Self {
11        safegcd::boxed::gcd::<false>(self, rhs)
12    }
13
14    fn gcd_vartime(&self, rhs: &Self) -> Self::Output {
15        safegcd::boxed::gcd::<true>(self, rhs)
16    }
17}
18
19impl Gcd<BoxedUint> for NonZero<BoxedUint> {
20    type Output = NonZero<BoxedUint>;
21
22    fn gcd(&self, rhs: &BoxedUint) -> Self::Output {
23        safegcd::boxed::gcd_nz::<false>(self, rhs)
24    }
25
26    fn gcd_vartime(&self, rhs: &BoxedUint) -> Self::Output {
27        safegcd::boxed::gcd_nz::<true>(self, rhs)
28    }
29}
30
31impl Gcd<BoxedUint> for Odd<BoxedUint> {
32    type Output = Odd<BoxedUint>;
33
34    fn gcd(&self, rhs: &BoxedUint) -> Self::Output {
35        safegcd::boxed::gcd_odd::<false>(self, rhs)
36    }
37
38    fn gcd_vartime(&self, rhs: &BoxedUint) -> Self::Output {
39        safegcd::boxed::gcd_odd::<true>(self, rhs)
40    }
41}
42
43#[cfg(test)]
44mod tests {
45    use crate::{BoxedUint, Gcd, Resize};
46
47    #[test]
48    fn gcd_relatively_prime() {
49        // Two semiprimes with no common factors
50        let f = BoxedUint::from(59u32 * 67).to_odd().unwrap();
51        let g = BoxedUint::from(61u32 * 71);
52        let gcd = f.gcd(&g);
53        assert_eq!(gcd.0, BoxedUint::one());
54    }
55
56    #[test]
57    fn gcd_nonprime() {
58        let f = BoxedUint::from(4391633u32).to_odd().unwrap();
59        let g = BoxedUint::from(2022161u32);
60        let gcd = f.gcd(&g);
61        assert_eq!(gcd.0, BoxedUint::from(1763u32));
62    }
63
64    #[test]
65    fn gcd_zero() {
66        let zero = BoxedUint::from(0u32);
67        let one = BoxedUint::from(1u32);
68
69        assert_eq!(zero.gcd(&zero), zero);
70        assert_eq!(zero.gcd(&one), one);
71        assert_eq!(one.gcd(&zero), one);
72    }
73
74    #[test]
75    fn gcd_one() {
76        let f = BoxedUint::from(1u32);
77        assert_eq!(BoxedUint::from(1u32), f.gcd(&BoxedUint::from(1u32)));
78        assert_eq!(BoxedUint::from(1u32), f.gcd(&BoxedUint::from(2u8)));
79    }
80
81    #[test]
82    fn gcd_two() {
83        let f = BoxedUint::from(2u32);
84        assert_eq!(f, f.gcd(&f));
85
86        let g = BoxedUint::from(4u32);
87        assert_eq!(f, f.gcd(&g));
88        assert_eq!(f, g.gcd(&f));
89    }
90
91    #[test]
92    fn gcd_different_sizes() {
93        // Test that gcd works for boxed Uints with different numbers of limbs
94        let f = BoxedUint::from(4391633u32).resize(128).to_odd().unwrap();
95        let g = BoxedUint::from(2022161u32);
96        let gcd = f.gcd(&g);
97        assert_eq!(gcd.0, BoxedUint::from(1763u32));
98    }
99
100    #[test]
101    fn gcd_vartime_different_sizes() {
102        // Test that gcd works for boxed Uints with different numbers of limbs
103        let f = BoxedUint::from(4391633u32).resize(128).to_odd().unwrap();
104        let g = BoxedUint::from(2022161u32);
105        let gcd = f.gcd_vartime(&g);
106        assert_eq!(gcd.0, BoxedUint::from(1763u32));
107    }
108}
crypto_bigint/uint/boxed/gcd.rs

crypto_bigint/uint/boxed/
gcd.rs
