crypto_bigint/int/
gcd.rs

1//! Support for computing the greatest common divisor of `Int`s.
2
3use crate::modular::SafeGcdInverter;
4use crate::{Gcd, Int, Odd, PrecomputeInverter, Uint};
5
6/// Gcd of two [Int]s
7impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Gcd for Int<SAT_LIMBS>
8where
9    Odd<Uint<SAT_LIMBS>>: PrecomputeInverter<Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>>,
10{
11    type Output = Uint<SAT_LIMBS>;
12
13    fn gcd(&self, rhs: &Self) -> Self::Output {
14        self.abs().gcd(&rhs.abs())
15    }
16
17    fn gcd_vartime(&self, rhs: &Self) -> Self::Output {
18        self.abs().gcd_vartime(&rhs.abs())
19    }
20}
21
22/// Gcd of an [Int] and a [Uint].
23impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Gcd<Uint<SAT_LIMBS>> for Int<SAT_LIMBS>
24where
25    Odd<Uint<SAT_LIMBS>>: PrecomputeInverter<Inverter = SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>>,
26{
27    type Output = Uint<SAT_LIMBS>;
28
29    fn gcd(&self, rhs: &Uint<SAT_LIMBS>) -> Self::Output {
30        self.abs().gcd(rhs)
31    }
32
33    fn gcd_vartime(&self, rhs: &Uint<SAT_LIMBS>) -> Self::Output {
34        self.abs().gcd_vartime(rhs)
35    }
36}
37
38#[cfg(test)]
39mod tests {
40    use crate::{Gcd, I256, U256};
41
42    #[test]
43    fn gcd_always_positive() {
44        // Two numbers with a shared factor of 61
45        let f = I256::from(59i32 * 61);
46        let g = I256::from(61i32 * 71);
47
48        assert_eq!(U256::from(61u32), f.gcd(&g));
49        assert_eq!(U256::from(61u32), f.wrapping_neg().gcd(&g));
50        assert_eq!(U256::from(61u32), f.gcd(&g.wrapping_neg()));
51        assert_eq!(U256::from(61u32), f.wrapping_neg().gcd(&g.wrapping_neg()));
52    }
53
54    #[test]
55    fn gcd_int_uint() {
56        // Two numbers with a shared factor of 61
57        let f = I256::from(59i32 * 61);
58        let g = U256::from(61u32 * 71);
59
60        assert_eq!(U256::from(61u32), f.gcd(&g));
61        assert_eq!(U256::from(61u32), f.wrapping_neg().gcd(&g));
62    }
63}
crypto_bigint/int/gcd.rs

crypto_bigint/int/
gcd.rs
