crypto-bigint 0.7.4

Pure Rust implementation of a big integer library which has been designed from the ground-up for use in cryptographic applications. Provides constant-time, no_std-friendly implementations of modern formulas using const generics.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

//! This module implements Least common multiple (LCM) for [`Uint`].

use crate::{Concat, Lcm, Uint};

impl<const LIMBS: usize> Uint<LIMBS> {
    /// Compute the least common multiple of `self` and `rhs`.
    #[must_use]
    pub const fn lcm<const WIDE_LIMBS: usize>(&self, rhs: &Self) -> Uint<WIDE_LIMBS>
    where
        Self: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
    {
        let (lhs_nz, _) = self.to_nz_or_one();
        let gcd_nz = lhs_nz.gcd_unsigned(rhs);
        self.div_exact(&gcd_nz)
            .expect_copied("invalid gcd")
            .concatenating_mul(rhs)
    }

    /// Compute the least common multiple of `self` and `rhs`.
    ///
    /// This method is variable time with respect to `self` and `rhs`.
    #[must_use]
    pub const fn lcm_vartime<const WIDE_LIMBS: usize>(&self, rhs: &Self) -> Uint<WIDE_LIMBS>
    where
        Self: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
    {
        let (Some(lhs_nz), false) = (self.as_nz_vartime(), rhs.is_zero_vartime()) else {
            return Uint::ZERO;
        };
        let gcd_nz = lhs_nz.gcd_unsigned_vartime(rhs);
        self.div_exact_vartime(&gcd_nz)
            .expect_copied("invalid gcd")
            .concatenating_mul(rhs)
    }
}

impl<const LIMBS: usize, const WIDE_LIMBS: usize> Lcm for Uint<LIMBS>
where
    Self: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
{
    type Output = Uint<WIDE_LIMBS>;

    fn lcm(&self, rhs: &Self) -> Self::Output {
        self.lcm(rhs)
    }

    fn lcm_vartime(&self, rhs: &Self) -> Self::Output {
        self.lcm_vartime(rhs)
    }
}

#[cfg(test)]
mod tests {
    mod lcm {
        use crate::{Concat, Lcm, U64, U128, U512, U1024, U4096, U8192, Uint};

        fn test<const LIMBS: usize, const WIDE_LIMBS: usize>(
            lhs: Uint<LIMBS>,
            rhs: Uint<LIMBS>,
            target: Uint<WIDE_LIMBS>,
        ) where
            Uint<LIMBS>: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
        {
            assert_eq!(lhs.lcm(&rhs), target);
            assert_eq!(lhs.lcm_vartime(&rhs), target);
            assert_eq!(Lcm::lcm(&lhs, &rhs), target);
            assert_eq!(Lcm::lcm_vartime(&lhs, &rhs), target);
        }

        fn run_tests<const LIMBS: usize, const WIDE_LIMBS: usize>()
        where
            Uint<LIMBS>: Concat<LIMBS, Output = Uint<WIDE_LIMBS>>,
        {
            test(Uint::<LIMBS>::ZERO, Uint::ZERO, Uint::<WIDE_LIMBS>::ZERO);
            test(Uint::<LIMBS>::ZERO, Uint::ONE, Uint::<WIDE_LIMBS>::ZERO);
            test(Uint::<LIMBS>::ZERO, Uint::MAX, Uint::<WIDE_LIMBS>::ZERO);
            test(Uint::<LIMBS>::ONE, Uint::ZERO, Uint::<WIDE_LIMBS>::ZERO);
            test(Uint::<LIMBS>::ONE, Uint::ONE, Uint::<WIDE_LIMBS>::ONE);
            test(
                Uint::<LIMBS>::ONE,
                Uint::MAX,
                Uint::<LIMBS>::MAX.resize::<WIDE_LIMBS>(),
            );
            test(Uint::<LIMBS>::MAX, Uint::ZERO, Uint::<WIDE_LIMBS>::ZERO);
            test(
                Uint::<LIMBS>::MAX,
                Uint::ONE,
                Uint::<LIMBS>::MAX.resize::<WIDE_LIMBS>(),
            );
            test(
                Uint::<LIMBS>::MAX,
                Uint::MAX,
                Uint::<LIMBS>::MAX.resize::<WIDE_LIMBS>(),
            );
        }

        #[test]
        fn lcm_sizes() {
            run_tests::<{ U64::LIMBS }, { U128::LIMBS }>();
            run_tests::<{ U512::LIMBS }, { U1024::LIMBS }>();
            if cfg!(not(miri)) {
                run_tests::<{ U4096::LIMBS }, { U8192::LIMBS }>();
            }
        }
    }
}