crypto-bigint 0.7.2

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

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

use crate::{Concat, NonZero, 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 self_is_nz = self.is_nonzero();
        let rhs_is_nz = rhs.is_nonzero();

        let gcd_nz = NonZero(self.gcd(&Uint::select(&Uint::ONE, rhs, rhs_is_nz)));

        let lcm = self.wrapping_div(&gcd_nz).concatenating_mul(rhs);

        Uint::select(&Uint::ZERO, &lcm, self_is_nz.and(rhs_is_nz))
    }
}

#[cfg(test)]
mod tests {
    mod lcm {
        use crate::{Concat, U64, U128, U256, U512, U1024, U2048, 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);
        }

        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::<{ U128::LIMBS }, { U256::LIMBS }>();
            run_tests::<{ U256::LIMBS }, { U512::LIMBS }>();
            run_tests::<{ U512::LIMBS }, { U1024::LIMBS }>();
            if cfg!(not(miri)) {
                run_tests::<{ U1024::LIMBS }, { U2048::LIMBS }>();
                run_tests::<{ U2048::LIMBS }, { U4096::LIMBS }>();
                run_tests::<{ U4096::LIMBS }, { U8192::LIMBS }>();
            }
        }
    }
}