crypto_bigint/uint/
gcd.rs

1//! Support for computing the greatest common divisor of two `Uint`s.
2
3use crate::{modular::SafeGcdInverter, ConstChoice, Gcd, Int, Odd, PrecomputeInverter, Uint};
4
5impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Uint<SAT_LIMBS>
6where
7    Odd<Self>: PrecomputeInverter<Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>>,
8{
9    /// Compute the greatest common divisor (GCD) of this number and another.
10    ///
11    /// Runs in a constant number of iterations depending on the maximum highest bit of either
12    /// `self` or `rhs`.
13    pub const fn gcd(&self, rhs: &Self) -> Self {
14        let k1 = self.trailing_zeros();
15        let k2 = rhs.trailing_zeros();
16
17        // Select the smaller of the two `k` values, making 2^k the common even divisor
18        let k = ConstChoice::from_u32_lt(k2, k1).select_u32(k1, k2);
19
20        // Decompose `self` and `rhs` into `s{1, 2} * 2^k` where either `s1` or `s2` is odd
21        let s1 = self.overflowing_shr(k).unwrap_or(Self::ZERO);
22        let s2 = rhs.overflowing_shr(k).unwrap_or(Self::ZERO);
23
24        let f = Self::select(&s1, &s2, s2.is_odd().not());
25        let g = Self::select(&s1, &s2, s2.is_odd());
26
27        <Odd<Self> as PrecomputeInverter>::Inverter::gcd(&f, &g)
28            .overflowing_shl(k)
29            .unwrap_or(Self::ZERO)
30    }
31}
32
33impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Odd<Uint<SAT_LIMBS>>
34where
35    Self: PrecomputeInverter<Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>>,
36{
37    /// Compute the greatest common divisor (GCD) of this number and another.
38    ///
39    /// Runs in variable time with respect to `rhs`.
40    pub const fn gcd_vartime(&self, rhs: &Uint<SAT_LIMBS>) -> Uint<SAT_LIMBS> {
41        <Self as PrecomputeInverter>::Inverter::gcd_vartime(self.as_ref(), rhs)
42    }
43}
44
45impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Gcd for Uint<SAT_LIMBS>
46where
47    Odd<Self>: PrecomputeInverter<Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>>,
48{
49    type Output = Uint<SAT_LIMBS>;
50
51    fn gcd(&self, rhs: &Self) -> Self {
52        self.gcd(rhs)
53    }
54
55    fn gcd_vartime(&self, rhs: &Self) -> Self::Output {
56        match Odd::<Self>::new(*self).into_option() {
57            Some(odd) => odd.gcd_vartime(rhs),
58            None => self.gcd(rhs), // TODO(tarcieri): vartime support for even `self`?
59        }
60    }
61}
62
63impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Gcd<Uint<SAT_LIMBS>> for Odd<Uint<SAT_LIMBS>>
64where
65    Odd<Self>: PrecomputeInverter<Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>>,
66{
67    type Output = Uint<SAT_LIMBS>;
68
69    fn gcd(&self, rhs: &Uint<SAT_LIMBS>) -> Uint<SAT_LIMBS> {
70        <Odd<Self> as PrecomputeInverter>::Inverter::gcd(self, rhs)
71    }
72
73    fn gcd_vartime(&self, rhs: &Uint<SAT_LIMBS>) -> Self::Output {
74        <Odd<Self> as PrecomputeInverter>::Inverter::gcd_vartime(self, rhs)
75    }
76}
77
78/// Gcd of a [Uint] and an [Int].
79impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Gcd<Int<SAT_LIMBS>> for Uint<SAT_LIMBS>
80where
81    Odd<Uint<SAT_LIMBS>>: PrecomputeInverter<Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>>,
82{
83    type Output = Uint<SAT_LIMBS>;
84
85    fn gcd(&self, rhs: &Int<SAT_LIMBS>) -> Self::Output {
86        self.gcd(&rhs.abs())
87    }
88
89    fn gcd_vartime(&self, rhs: &Int<SAT_LIMBS>) -> Self::Output {
90        self.gcd_vartime(&rhs.abs())
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    use crate::{Gcd, I256, U256};
97
98    #[test]
99    fn gcd_relatively_prime() {
100        // Two semiprimes with no common factors
101        let f = U256::from(59u32 * 67);
102        let g = U256::from(61u32 * 71);
103        let gcd = f.gcd(&g);
104        assert_eq!(gcd, U256::ONE);
105    }
106
107    #[test]
108    fn gcd_nonprime() {
109        let f = U256::from(4391633u32);
110        let g = U256::from(2022161u32);
111        let gcd = f.gcd(&g);
112        assert_eq!(gcd, U256::from(1763u32));
113    }
114
115    #[test]
116    fn gcd_zero() {
117        assert_eq!(U256::ZERO.gcd(&U256::ZERO), U256::ZERO);
118        assert_eq!(U256::ZERO.gcd(&U256::ONE), U256::ONE);
119        assert_eq!(U256::ONE.gcd(&U256::ZERO), U256::ONE);
120    }
121
122    #[test]
123    fn gcd_one() {
124        let f = U256::ONE;
125        assert_eq!(U256::ONE, f.gcd(&U256::ONE));
126        assert_eq!(U256::ONE, f.gcd(&U256::from(2u8)));
127    }
128
129    #[test]
130    fn gcd_two() {
131        let f = U256::from_u8(2);
132        assert_eq!(f, f.gcd(&f));
133
134        let g = U256::from_u8(4);
135        assert_eq!(f, f.gcd(&g));
136        assert_eq!(f, g.gcd(&f));
137    }
138
139    #[test]
140    fn gcd_uint_int() {
141        // Two numbers with a shared factor of 61
142        let f = U256::from(61u32 * 71);
143        let g = I256::from(59i32 * 61);
144
145        let sixty_one = U256::from(61u32);
146        assert_eq!(sixty_one, <U256 as Gcd<I256>>::gcd(&f, &g));
147        assert_eq!(sixty_one, <U256 as Gcd<I256>>::gcd(&f, &g.wrapping_neg()));
148    }
149}
crypto_bigint/uint/gcd.rs

crypto_bigint/uint/
gcd.rs
