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, Limb, 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.get(), 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.get(), 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_zero_lhs_wider_than_rhs() {
76        let zero = BoxedUint::zero_with_precision(2 * Limb::BITS);
77        let one = BoxedUint::one();
78
79        let gcd = zero.gcd(&one);
80        assert_eq!(gcd, one);
81        assert_eq!(gcd.bits_precision(), zero.bits_precision());
82    }
83
84    #[test]
85    fn gcd_zero_rhs_wider_than_lhs() {
86        let one = BoxedUint::one();
87        let zero = BoxedUint::zero_with_precision(2 * Limb::BITS);
88
89        let gcd = one.gcd(&zero);
90        assert_eq!(gcd, one);
91    }
92
93    #[test]
94    fn gcd_zero_rhs_narrower_than_power_of_two_lhs() {
95        let x = BoxedUint::one_with_precision(3 * Limb::BITS).wrapping_shl_vartime(Limb::BITS + 1);
96        let zero = BoxedUint::zero_with_precision(Limb::BITS);
97
98        let gcd = x.gcd(&zero);
99        assert_eq!(gcd, x);
100    }
101
102    #[test]
103    fn gcd_vartime_zero_rhs_narrower_than_power_of_two_lhs() {
104        let x = BoxedUint::one_with_precision(3 * Limb::BITS).wrapping_shl_vartime(Limb::BITS + 1);
105        let zero = BoxedUint::zero_with_precision(Limb::BITS);
106
107        let gcd = x.gcd_vartime(&zero);
108        assert_eq!(gcd, x);
109    }
110
111    #[test]
112    fn gcd_nonzero_lhs_wider_than_rhs_precision() {
113        let wide = BoxedUint::from(6u8).resize(2 * Limb::BITS);
114        let narrow = BoxedUint::from(4u8);
115
116        let gcd = wide.gcd(&narrow);
117        assert_eq!(gcd, BoxedUint::from(2u8));
118        assert_eq!(gcd.bits_precision(), wide.bits_precision());
119    }
120
121    #[test]
122    fn gcd_nonzero_rhs_wider_than_lhs_precision() {
123        let narrow = BoxedUint::from(4u8);
124        let wide = BoxedUint::from(6u8).resize(2 * Limb::BITS);
125
126        let gcd = narrow.gcd(&wide);
127        assert_eq!(gcd, BoxedUint::from(2u8));
128        assert_eq!(gcd.bits_precision(), wide.bits_precision());
129    }
130
131    #[test]
132    fn gcd_vartime_zero_lhs_wider_than_rhs() {
133        let zero = BoxedUint::zero_with_precision(2 * Limb::BITS);
134        let one = BoxedUint::one();
135
136        let gcd = zero.gcd_vartime(&one);
137        assert_eq!(gcd, one);
138        assert_eq!(gcd.bits_precision(), zero.bits_precision());
139    }
140
141    #[test]
142    fn gcd_vartime_zero_rhs_wider_than_lhs() {
143        let one = BoxedUint::one();
144        let zero = BoxedUint::zero_with_precision(2 * Limb::BITS);
145
146        let gcd = one.gcd_vartime(&zero);
147        assert_eq!(gcd, one);
148        assert_eq!(gcd.bits_precision(), zero.bits_precision());
149    }
150
151    #[test]
152    fn gcd_zero_zero_mixed_precision() {
153        let narrow = BoxedUint::zero_with_precision(Limb::BITS);
154        let wide = BoxedUint::zero_with_precision(2 * Limb::BITS);
155
156        let gcd = narrow.gcd(&wide);
157        assert_eq!(gcd, narrow);
158        assert_eq!(gcd.bits_precision(), wide.bits_precision());
159        assert_eq!(gcd, wide.gcd(&narrow));
160    }
161
162    #[test]
163    fn gcd_vartime_zero_zero_mixed_precision() {
164        let narrow = BoxedUint::zero_with_precision(Limb::BITS);
165        let wide = BoxedUint::zero_with_precision(2 * Limb::BITS);
166
167        let gcd = narrow.gcd_vartime(&wide);
168        assert_eq!(gcd, narrow);
169        assert_eq!(gcd.bits_precision(), wide.bits_precision());
170        assert_eq!(gcd, wide.gcd_vartime(&narrow));
171    }
172
173    #[test]
174    fn gcd_one() {
175        let f = BoxedUint::from(1u32);
176        assert_eq!(BoxedUint::from(1u32), f.gcd(&BoxedUint::from(1u32)));
177        assert_eq!(BoxedUint::from(1u32), f.gcd(&BoxedUint::from(2u8)));
178    }
179
180    #[test]
181    fn gcd_two() {
182        let f = BoxedUint::from(2u32);
183        assert_eq!(f, f.gcd(&f));
184
185        let g = BoxedUint::from(4u32);
186        assert_eq!(f, f.gcd(&g));
187        assert_eq!(f, g.gcd(&f));
188    }
189
190    #[test]
191    fn gcd_different_sizes() {
192        // Test that gcd works for boxed Uints with different numbers of limbs
193        let f = BoxedUint::from(4391633u32).resize(128).to_odd().unwrap();
194        let g = BoxedUint::from(2022161u32);
195        let gcd = f.gcd(&g);
196        assert_eq!(gcd.get(), BoxedUint::from(1763u32));
197    }
198
199    #[test]
200    fn gcd_vartime_different_sizes() {
201        // Test that gcd works for boxed Uints with different numbers of limbs
202        let f = BoxedUint::from(4391633u32).resize(128).to_odd().unwrap();
203        let g = BoxedUint::from(2022161u32);
204        let gcd = f.gcd_vartime(&g);
205        assert_eq!(gcd.get(), BoxedUint::from(1763u32));
206    }
207}
crypto_bigint/uint/boxed/gcd.rs

crypto_bigint/uint/boxed/
gcd.rs
