crypto_bigint/uint/boxed/
gcd.rs

1//! Support for computing greatest common divisor of two `BoxedUint`s.
2
3use super::BoxedUint;
4use crate::{modular::safegcd, ConstantTimeSelect, Gcd, Integer, Odd};
5use subtle::{ConditionallySelectable, ConstantTimeLess};
6
7impl Gcd for BoxedUint {
8    type Output = Self;
9
10    /// Compute the greatest common divisor (GCD) of this number and another.
11    fn gcd(&self, rhs: &Self) -> Self {
12        let k1 = self.trailing_zeros();
13        let k2 = rhs.trailing_zeros();
14
15        // Select the smaller of the two `k` values, making 2^k the common even divisor
16        let k = u32::conditional_select(&k1, &k2, u32::ct_lt(&k2, &k1));
17
18        // Decompose `self` and `rhs` into `s{1, 2} * 2^k` where either `s1` or `s2` is odd
19        let s1 = self.overflowing_shr(k).0;
20        let s2 = rhs.overflowing_shr(k).0;
21
22        let f = Self::ct_select(&s1, &s2, !s2.is_odd());
23        let g = Self::ct_select(&s1, &s2, s2.is_odd());
24        safegcd::boxed::gcd(&f, &g).overflowing_shl(k).0
25    }
26
27    fn gcd_vartime(&self, rhs: &Self) -> Self::Output {
28        match Odd::<Self>::new(self.clone()).into_option() {
29            Some(odd) => odd.gcd_vartime(rhs),
30            None => self.gcd(rhs), // TODO(tarcieri): vartime support for even `self`?
31        }
32    }
33}
34
35impl Gcd<BoxedUint> for Odd<BoxedUint> {
36    type Output = BoxedUint;
37
38    fn gcd(&self, rhs: &BoxedUint) -> BoxedUint {
39        safegcd::boxed::gcd(self, rhs)
40    }
41
42    fn gcd_vartime(&self, rhs: &BoxedUint) -> Self::Output {
43        safegcd::boxed::gcd_vartime(self, rhs)
44    }
45}
46
47#[cfg(test)]
48mod tests {
49    use crate::{BoxedUint, Gcd};
50
51    #[test]
52    fn gcd_relatively_prime() {
53        // Two semiprimes with no common factors
54        let f = BoxedUint::from(59u32 * 67).to_odd().unwrap();
55        let g = BoxedUint::from(61u32 * 71);
56        let gcd = f.gcd(&g);
57        assert_eq!(gcd, BoxedUint::one());
58    }
59
60    #[test]
61    fn gcd_nonprime() {
62        let f = BoxedUint::from(4391633u32).to_odd().unwrap();
63        let g = BoxedUint::from(2022161u32);
64        let gcd = f.gcd(&g);
65        assert_eq!(gcd, BoxedUint::from(1763u32));
66    }
67
68    #[test]
69    fn gcd_zero() {
70        let zero = BoxedUint::from(0u32);
71        let one = BoxedUint::from(1u32);
72
73        assert_eq!(zero.gcd(&zero), zero);
74        assert_eq!(zero.gcd(&one), one);
75        assert_eq!(one.gcd(&zero), one);
76    }
77
78    #[test]
79    fn gcd_one() {
80        let f = BoxedUint::from(1u32);
81        assert_eq!(BoxedUint::from(1u32), f.gcd(&BoxedUint::from(1u32)));
82        assert_eq!(BoxedUint::from(1u32), f.gcd(&BoxedUint::from(2u8)));
83    }
84
85    #[test]
86    fn gcd_two() {
87        let f = BoxedUint::from(2u32);
88        assert_eq!(f, f.gcd(&f));
89
90        let g = BoxedUint::from(4u32);
91        assert_eq!(f, f.gcd(&g));
92        assert_eq!(f, g.gcd(&f));
93    }
94
95    #[test]
96    fn gcd_different_sizes() {
97        // Test that gcd works for boxed Uints with different numbers of limbs
98        let f = BoxedUint::from(4391633u32).widen(128).to_odd().unwrap();
99        let g = BoxedUint::from(2022161u32);
100        let gcd = f.gcd(&g);
101        assert_eq!(gcd, BoxedUint::from(1763u32));
102    }
103
104    #[test]
105    fn gcd_vartime_different_sizes() {
106        // Test that gcd works for boxed Uints with different numbers of limbs
107        let f = BoxedUint::from(4391633u32).widen(128).to_odd().unwrap();
108        let g = BoxedUint::from(2022161u32);
109        let gcd = f.gcd_vartime(&g);
110        assert_eq!(gcd, BoxedUint::from(1763u32));
111    }
112}
crypto_bigint/uint/boxed/gcd.rs

crypto_bigint/uint/boxed/
gcd.rs
