28725835473

Committed 05 Jul 2026 01:35AM UTC coverage: 98.698% (+0.1%) from 98.55%

Build # 28725835473

Build Type

Pull #23

github

Committed by

web-flow

Commit Message

Merge 3d73b5eb0 into 32599a022

Pull Request Pull Request #23: v0.4.0: const-num-traits migration, CT typestate discipline, safegcd CT inverse

Coverage Stats

1735 of 1761 new or added lines in 14 files covered. (98.52%)

15 existing lines in 2 files now uncovered.

5989 of 6068 relevant lines covered (98.7%)

3089.95 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.49

/modmath/src/exp.rs

#[cfg(feature = "nightly")]
use super::mul::const_mod_mul;
use super::mul::{basic_mod_mul_pr, constrained_mod_mul_pr, strict_mod_mul_pr};

#[cfg(feature = "nightly")]
use const_num_traits::{One, OverflowingAdd, OverflowingSub, Zero};

#[cfg(feature = "nightly")]
c0nst::c0nst! {
    /// # Const Modular Exponentiation
    /// Const-evaluable version of modular exponentiation.
    pub c0nst fn const_mod_exp<T>(mut base: T, exponent: T, modulus: T) -> T
    where
        T: [c0nst] core::cmp::PartialOrd
            + [c0nst] core::cmp::PartialEq
            + Copy
            + [c0nst] Zero
            + [c0nst] One
            + [c0nst] core::ops::BitAnd<Output = T>
            + [c0nst] OverflowingAdd
            + [c0nst] core::ops::Add<Output = T>
            + [c0nst] OverflowingSub
            + [c0nst] core::ops::Sub<Output = T>
            + [c0nst] core::ops::Shr<usize, Output = T>
            + [c0nst] core::ops::ShrAssign<usize>
            + [c0nst] core::ops::Rem<Output = T>,
    {
        let mut result = T::one() % modulus;
        let mut exp = exponent;

        base = base % modulus;

        while exp > T::zero() {
            if exp & T::one() == T::one() {
                result = const_mod_mul(result, base, modulus);
            }
            exp >>= 1;

            if exp > T::zero() {
                base = const_mod_mul(base, base, modulus);
            }
        }
        result
    }
}

/// # Modular Exponentiation (Basic)
/// Simple version that operates on values and copies them. Requires
/// `WrappingAdd` and `WrappingSub` traits to be implemented.
pub fn basic_mod_exp<T>(base: T, exponent: T, modulus: T) -> T
where
    T: PartialOrd
        + const_num_traits::One
        + const_num_traits::Zero
        + crate::parity::Parity
        + core::ops::Rem<Output = T>
        + core::ops::Shr<usize, Output = T>
        + const_num_traits::ops::wrapping::WrappingAdd
        + const_num_traits::ops::wrapping::WrappingSub
        + core::ops::Add<Output = T>
        + core::ops::Sub<Output = T>
        + core::ops::ShrAssign<usize>
        + Copy
        + crate::NonCt,
{
    if modulus == T::one() {
        return T::zero();
    }
    basic_mod_exp_pr(base % modulus, exponent, modulus)
}

/// # Modular Exponentiation (Basic, proven-non-zero modulus). **Infallible.**
///
/// The `modulus == 1` early-return is preserved (any `x mod 1 == 0`) —
/// `T::NonZero` proves `modulus != 0`, not `modulus > 1`.
pub fn basic_mod_exp_nz<T>(base: T, exponent: T, modulus: T::NonZero) -> T
where
    T: PartialOrd
        + const_num_traits::One
        + const_num_traits::Zero
        + crate::parity::Parity
        + const_num_traits::HasNonZero
        + const_num_traits::DivNonZero<Output = T>
        + core::ops::Shr<usize, Output = T>
        + const_num_traits::ops::wrapping::WrappingAdd
        + const_num_traits::ops::wrapping::WrappingSub
        + core::ops::Add<Output = T>
        + core::ops::Sub<Output = T>
        + core::ops::ShrAssign<usize>
        + Copy
        + crate::NonCt,
{
    let m_raw = T::nonzero_get(modulus);
    if m_raw == T::one() {
        return T::zero();
    }
    basic_mod_exp_pr(base.rem_nonzero(modulus), exponent, m_raw)
}

/// # Modular Exponentiation (Basic, pre-reduced)
/// Precondition: if `modulus > 1`, then `base < modulus`. No `Rem` bound.
/// Returns `0` when `modulus == 1`.
///
/// Note: this only removes the division side-channel from the signature.
/// The square-and-multiply loop still branches on `exp.is_odd()`; for a
/// constant-time ladder, use the Montgomery wide-REDC path.
pub fn basic_mod_exp_pr<T>(mut base: T, exponent: T, modulus: T) -> T
where
    T: PartialOrd
        + const_num_traits::One
        + const_num_traits::Zero
        + crate::parity::Parity
        + core::ops::Shr<usize, Output = T>
        + const_num_traits::ops::wrapping::WrappingAdd
        + const_num_traits::ops::wrapping::WrappingSub
        + core::ops::Add<Output = T>
        + core::ops::Sub<Output = T>
        + core::ops::ShrAssign<usize>
        + Copy
        + crate::NonCt,
{
    // x mod 1 == 0 for every x, including 1. The square-and-multiply loop
    // below starts with `result = T::one()` and would return 1 in that case.
    if modulus == T::one() {
        return T::zero();
    }
    let mut result = T::one();
    let mut exp = exponent;

    while exp > T::zero() {
        if exp.is_odd() {
            result = basic_mod_mul_pr(result, base, modulus);
        }
        exp >>= 1;

        if exp > T::zero() {
            base = basic_mod_mul_pr(base, base, modulus);
        }
    }
    result
}

/// # Modular Exponentiation (Constrained)
/// Version that works with references, requires `WrappingAdd` and
/// `WrappingSub` traits to be implemented.
pub fn constrained_mod_exp<T>(mut base: T, exponent: &T, modulus: &T) -> T
where
    T: Copy
        + PartialOrd
        + const_num_traits::One
        + const_num_traits::Zero
        + crate::parity::Parity
        + const_num_traits::ops::wrapping::WrappingAdd
        + const_num_traits::ops::wrapping::WrappingSub
        + core::ops::Add<Output = T>
        + core::ops::Sub<Output = T>
        + core::ops::ShrAssign<usize>
        + core::ops::Shr<usize, Output = T>
        + crate::NonCt,
    for<'a> T: core::ops::RemAssign<&'a T>
        + core::ops::DivAssign<&'a T>
        + core::ops::Rem<&'a T, Output = T>,
    for<'a> &'a T: core::ops::Rem<&'a T, Output = T>,
{
    if modulus == &T::one() {
        return T::zero();
    }
    base.rem_assign(modulus);
    constrained_mod_exp_pr(base, exponent, modulus)
}

/// # Modular Exponentiation (Constrained, proven-non-zero modulus). **Infallible.**
pub fn constrained_mod_exp_nz<T>(base: T, exponent: &T, modulus: T::NonZero) -> T
where
    T: Copy
        + PartialOrd
        + const_num_traits::One
        + const_num_traits::Zero
        + crate::parity::Parity
        + const_num_traits::HasNonZero
        + const_num_traits::DivNonZero<Output = T>
        + const_num_traits::ops::wrapping::WrappingAdd
        + const_num_traits::ops::wrapping::WrappingSub
        + core::ops::Add<Output = T>
        + core::ops::Sub<Output = T>
        + core::ops::ShrAssign<usize>
        + core::ops::Shr<usize, Output = T>
        + crate::NonCt,
{
    let m_raw = T::nonzero_get(modulus);
    if m_raw == T::one() {
        return T::zero();
    }
    constrained_mod_exp_pr(base.rem_nonzero(modulus), exponent, &m_raw)
}

/// # Modular Exponentiation (Constrained, pre-reduced)
/// Precondition: if `*modulus > 1`, then `base < *modulus`. No `Rem` family bound.
/// Returns `0` when `*modulus == 1`.
pub fn constrained_mod_exp_pr<T>(mut base: T, exponent: &T, modulus: &T) -> T
where
    T: Copy
        + PartialOrd
        + const_num_traits::One
        + const_num_traits::Zero
        + crate::parity::Parity
        + const_num_traits::ops::wrapping::WrappingAdd
        + const_num_traits::ops::wrapping::WrappingSub
        + core::ops::Add<Output = T>
        + core::ops::Sub<Output = T>
        + core::ops::ShrAssign<usize>
        + core::ops::Shr<usize, Output = T>
        + crate::NonCt,
{
    // See `basic_mod_exp_pr` for the modulus==1 rationale.
    if modulus == &T::one() {
        return T::zero();
    }
    let mut result = T::one();
    let mut exp = T::zero().wrapping_add(*exponent);
    while exp > T::zero() {
        if exp.is_odd() {
            result = constrained_mod_mul_pr(result, &base, modulus);
        }
        exp >>= 1;
        if exp > T::zero() {
            // Squaring step: `mul_pr` consumes `a` (first arg) and borrows
            // `b` (second arg); when both come from the same `base`, we
            // still need one clone so the borrow doesn't alias the move.
            let tmp_base = T::zero().wrapping_add(base);
            base = constrained_mod_mul_pr(base, &tmp_base, modulus);
        }
    }
    result
}

/// # Modular Exponentiation (Strict)
/// Most constrained version that works with references. Requires
/// `OverflowingAdd` and `OverflowingSub` traits to be implemented, and
/// all multiplication contraints as well.
pub fn strict_mod_exp<T>(mut base: T, exponent: &T, modulus: &T) -> T
where
    T: Copy
        + PartialOrd
        + const_num_traits::One
        + const_num_traits::Zero
        + crate::parity::Parity
        + const_num_traits::ops::overflowing::OverflowingAdd
        + const_num_traits::ops::overflowing::OverflowingSub
        + core::ops::Add<Output = T>
        + core::ops::Sub<Output = T>
        + core::ops::Shr<usize, Output = T>
        + crate::NonCt,
    for<'a> T: core::ops::RemAssign<&'a T>
        + core::ops::DivAssign<&'a T>
        + core::ops::ShrAssign<usize>
        + core::ops::Rem<&'a T, Output = T>,
    for<'a> &'a T: core::ops::Rem<&'a T, Output = T>,
{
    if modulus == &T::one() {
        return T::zero();
    }
    base.rem_assign(modulus);
    strict_mod_exp_pr(base, exponent, modulus)
}

/// # Modular Exponentiation (Strict, proven-non-zero modulus). **Infallible.**
pub fn strict_mod_exp_nz<T>(base: T, exponent: &T, modulus: T::NonZero) -> T
where
    T: Copy
        + PartialOrd
        + const_num_traits::One
        + const_num_traits::Zero
        + crate::parity::Parity
        + const_num_traits::HasNonZero
        + const_num_traits::DivNonZero<Output = T>
        + const_num_traits::ops::overflowing::OverflowingAdd
        + const_num_traits::ops::overflowing::OverflowingSub
        + core::ops::Add<Output = T>
        + core::ops::Sub<Output = T>
        + core::ops::Shr<usize, Output = T>
        + crate::NonCt,
    for<'a> T: core::ops::ShrAssign<usize>,
{
    let m_raw = T::nonzero_get(modulus);
    if m_raw == T::one() {
        return T::zero();
    }
    strict_mod_exp_pr(base.rem_nonzero(modulus), exponent, &m_raw)
}

/// # Modular Exponentiation (Strict, pre-reduced)
/// Precondition: if `*modulus > 1`, then `base < *modulus`. No `Rem` family bound.
/// Returns `0` when `*modulus == 1`.
pub fn strict_mod_exp_pr<T>(mut base: T, exponent: &T, modulus: &T) -> T
where
    T: Copy
        + PartialOrd
        + const_num_traits::One
        + const_num_traits::Zero
        + crate::parity::Parity
        + const_num_traits::ops::overflowing::OverflowingAdd
        + const_num_traits::ops::overflowing::OverflowingSub
        + core::ops::Add<Output = T>
        + core::ops::Sub<Output = T>
        + core::ops::Shr<usize, Output = T>
        + crate::NonCt,
    for<'a> T: core::ops::ShrAssign<usize>,
{
    // See `basic_mod_exp_pr` for the modulus==1 rationale.
    if modulus == &T::one() {
        return T::zero();
    }
    let mut result = T::one();
    let mut exp = T::zero().overflowing_add(*exponent).0;

    while exp > T::zero() {
        if exp.is_odd() {
            result = strict_mod_mul_pr(result, &base, modulus);
        }
        exp >>= 1;

        if exp > T::zero() {
            // Squaring step: `mul_pr` consumes `a` (first arg) and borrows
            // `b` (second arg); when both come from the same `base`, we
            // still need one clone so the borrow doesn't alias the move.
            let tmp_base = T::zero().overflowing_add(base).0;
            base = strict_mod_mul_pr(base, &tmp_base, modulus);
        }
    }
    result
}

#[cfg(test)]
macro_rules! select_mod_exp {
    ($mod_exp:path, $t:ty, by_ref) => {
        fn mod_exp(a: $t, b: &$t, m: &$t) -> $t {
            $mod_exp(a, b, m)
        }
    };
    ($mod_exp:path, $t:ty, by_val) => {
        fn mod_exp(a: $t, b: &$t, m: &$t) -> $t {
            $mod_exp(a, *b, *m)
        }
    };
}

#[cfg(test)]
macro_rules! generate_mod_exp_tests_block_64 {
    ($mod_add:path, $t:ty, $by_ref:tt) => {
        select_mod_exp!($mod_add, $t, $by_ref);

        #[test]
        fn test_basic_small_values() {
            assert_eq!(mod_exp(2_u64, &3_u64, &5_u64), 3_u64); // 2^3 % 5 = 8 % 5 = 3
            assert_eq!(mod_exp(5_u64, &0_u64, &7_u64), 1_u64); // 5^0 % 7 = 1
        }

        #[test]
        fn test_basic_base_or_exponent_1() {
            assert_eq!(mod_exp(1_u64, &10_u64, &7_u64), 1_u64); // 1^10 % 7 = 1
            assert_eq!(mod_exp(7_u64, &1_u64, &13_u64), 7_u64); // 7^1 % 13 = 7
        }

        #[test]
        fn test_identity_modulus_of_1() {
            assert_eq!(mod_exp(10_u64, &10_u64, &1_u64), 0_u64); // Any number % 1 = 0
        }

        #[test]
        fn test_identity_exponent_of_0() {
            assert_eq!(mod_exp(5_u64, &0_u64, &9_u64), 1_u64); // 5^0 % 9 = 1
        }

        #[test]
        fn test_identity_exponent_of_0_modulus_of_1() {
            assert_eq!(mod_exp(5_u64, &0_u64, &1_u64), 0_u64); // 5^0 % 1 = 0
            assert_eq!(mod_exp(0_u64, &0_u64, &1_u64), 0_u64); // 0^0 % 1 = 0
        }

        #[test]
        fn test_identity_zero_to_the_zero() {
            // Handle 0^0 case based on how it's defined in your mod_exp implementation.
            assert_eq!(mod_exp(0_u64, &0_u64, &7_u64), 1_u64); // This assumes 0^0 = 1
        }

        #[test]
        fn test_edge_max_u64_values() {
            assert_eq!(mod_exp(u64::MAX, &2_u64, &u64::MAX), 0_u64); // (2^63 - 1)^2 % (2^63 - 1) = 0
            assert_eq!(
                mod_exp(u64::MAX, &2_u64, &1_000_000_007_u64),
                114_944_269_u64
            );
            // Big exponent mod test
        }

        #[test]
        fn test_edge_base_of_zero() {
            assert_eq!(mod_exp(0_u64, &10_u64, &7_u64), 0_u64); // 0^10 % 7 = 0
        }

        #[test]
        fn test_prime_modulus() {
            assert_eq!(mod_exp(7_u64, &13_u64, &19_u64), 7_u64); // 7^13 % 19 = 7
            assert_eq!(mod_exp(3_u64, &13_u64, &17_u64), 12_u64); // 3^13 % 17 = 12
        }

        #[test]
        fn test_large_exponent() {
            // This test assumes efficient modular exponentiation like exponentiation by squaring.
            assert_eq!(mod_exp(7_u64, &(1 << 20), &13_u64), 9_u64); // 7^2^20 % 13 = 9
        }

        #[test]
        fn test_overflow_handling() {
            assert_eq!(mod_exp(2_u64.pow(32), &2_u64.pow(32), &97_u64), 35_u64); // Big exponent/modulus
            assert_eq!(
                mod_exp(2_u64.pow(63), &2_u64.pow(63), &1_000_000_007_u64),
                719_537_220_u64
            );
        }

        #[test]
        fn test_coprime_values() {
            assert_eq!(
                mod_exp(123_456_789_u64, &987_654_321_u64, &1_000_000_007_u64),
                652_541_198_u64
            );
        }
    };
}

#[cfg(test)]
macro_rules! generate_mod_exp_tests_block_8 {
    ($mod_add:path, $t:ty, $by_ref:tt) => {
        select_mod_exp!($mod_add, $t, $by_ref);

        #[test]
        fn test_edge_max_u8_values() {
            // Equivalent of mod_exp(u64::MAX, 2_u64, u64::MAX) with u8
            assert_eq!(mod_exp(u8::MAX, &2_u8, &u8::MAX), 0_u8); // (255^2) % 255 = 0
            assert_eq!(mod_exp(u8::MAX, &2_u8, &97_u8), 35_u8); // (255^2) % 97 = 35
        }

        #[test]
        fn test_big_exponent_mod_u8() {
            assert_eq!(mod_exp(u8::MAX, &2_u8, &97_u8), 35_u8); // (255^2) % 97 = 35
        }

        #[test]
        fn test_overflow_handling_u8() {
            // Equivalent of mod_exp(2^32, 2^32, 97) with u8
            assert_eq!(mod_exp(2_u8.pow(4), &2_u8.pow(4), &97_u8), 61_u8); // (16^16) % 97 = 61
        }

        #[test]
        fn test_prime_modulus_u8() {
            // Equivalent of mod_exp(7_u64, 13_u64, 19_u64) with u8
            assert_eq!(mod_exp(7_u8, &13_u8, &19_u8), 7_u8); // 7^13 % 19 = 7
        }
    };
}
#[cfg(test)]
macro_rules! generate_mod_exp_tests_block_16 {
    ($mod_add:path, $t:ty, $by_ref:tt) => {
        select_mod_exp!($mod_add, $t, $by_ref);

        #[test]
        fn test_edge_max_u16_values() {
            // Equivalent of mod_exp(u64::MAX, 2_u64, u64::MAX) with u16
            assert_eq!(mod_exp(u16::MAX, &2_u16, &u16::MAX), 0_u16); // (65535^2) % 65535 = 0
        }
    };
}

#[cfg(test)]
macro_rules! generate_mod_exp_tests_block_32 {
    ($mod_add:path, $t:ty, $by_ref:tt) => {
        select_mod_exp!($mod_add, $t, $by_ref);

        #[test]
        fn test_edge_max_u32_values() {
            // Equivalent of mod_exp(u64::MAX, 2_u64, u64::MAX) with u32
            assert_eq!(mod_exp(u32::MAX, &2_u32, &u32::MAX), 0_u32); // (4294967295^2) % 4294967295 = 0
        }
    };
}

#[cfg(test)]
mod strict_mod_exp_tests {
    use super::strict_mod_exp;
    mod u64_tests {
        generate_mod_exp_tests_block_64!(super::strict_mod_exp, u64, by_ref);
    }
    mod u8_tests {
        generate_mod_exp_tests_block_8!(super::strict_mod_exp, u8, by_ref);
    }
    mod u16_tests {
        generate_mod_exp_tests_block_16!(super::strict_mod_exp, u16, by_ref);
    }
    mod u32_tests {
        generate_mod_exp_tests_block_32!(super::strict_mod_exp, u32, by_ref);
    }
}

#[cfg(test)]
mod constrained_mod_exp_tests {
    use super::constrained_mod_exp;

    mod u64_tests {
        generate_mod_exp_tests_block_64!(super::constrained_mod_exp, u64, by_ref);
    }
    mod u8_tests {
        generate_mod_exp_tests_block_8!(super::constrained_mod_exp, u8, by_ref);
    }
    mod u16_tests {
        generate_mod_exp_tests_block_16!(super::constrained_mod_exp, u16, by_ref);
    }
    mod u32_tests {
        generate_mod_exp_tests_block_32!(super::constrained_mod_exp, u32, by_ref);
    }
}

#[cfg(test)]
mod basic_mod_exp_tests {
    use super::basic_mod_exp;

    mod u64_tests {
        generate_mod_exp_tests_block_64!(super::basic_mod_exp, u64, by_val);
    }
    mod u8_tests {
        generate_mod_exp_tests_block_8!(super::basic_mod_exp, u8, by_val);
    }
    mod u16_tests {
        generate_mod_exp_tests_block_16!(super::basic_mod_exp, u16, by_val);
    }
    mod u32_tests {
        generate_mod_exp_tests_block_32!(super::basic_mod_exp, u32, by_val);
    }
}

#[cfg(test)]
#[cfg(feature = "nightly")]
const _: () = {
    let result = const_mod_exp(2u64, 3u64, 5u64);
    assert!(result == 3u64);
};

#[cfg(test)]
#[cfg(feature = "nightly")]
mod const_mod_exp_tests {
    use super::const_mod_exp;

    mod u64_tests {
        generate_mod_exp_tests_block_64!(super::const_mod_exp, u64, by_val);
    }
    mod u8_tests {
        generate_mod_exp_tests_block_8!(super::const_mod_exp, u8, by_val);
    }
    mod u16_tests {
        generate_mod_exp_tests_block_16!(super::const_mod_exp, u16, by_val);
    }
    mod u32_tests {
        generate_mod_exp_tests_block_32!(super::const_mod_exp, u32, by_val);
    }
}

#[cfg(test)]
macro_rules! exp_test_module {
    (
        $stem:ident,           // Base name (e.g., "bnum")
        $type_path:path,       // Full path to the type
        $(type $type_def:ty = $type_expr:ty;)? // Optional type definition
        strict: $strict:expr,
        constrained: $constrained:expr,
        basic: $basic:expr,
    ) => {
        paste::paste! {
            mod [<$stem _tests>] {     // This creates e.g., mod bnum_tests
                #[allow(unused_imports)]
                use $type_path;
                $( type $type_def = $type_expr; )?

                #[test]
                #[allow(unused_variables)]
                fn test_mod_exp_basic() {
                    let a = U256::from(5u8);
                    let b = U256::from(3u8);
                    let m = U256::from(13u8);

                    // pow(5,3,13)
                    let a_val = 5u8;
                    let a = U256::from(a_val);
                    let b = U256::from(3u8);
                    let m = U256::from(13u8);
                    let result = U256::from(8u8);

                    crate::maybe_test!($strict, assert_eq!(super::strict_mod_exp(a, &b, &m), result));
                    let a = U256::from(a_val);
                    crate::maybe_test!($constrained, assert_eq!(super::constrained_mod_exp(a, &b, &m), result));
                    let a = U256::from(a_val);
                    crate::maybe_test!($basic, assert_eq!(super::basic_mod_exp(a, b, m), result));

                    // pow(123,45,1000)
                    let a_val = 123u8;
                    let a = U256::from(a_val);
                    let b = U256::from(45u8);
                    let m = U256::from(1000u16);
                    let result = U256::from(43u16);

                    crate::maybe_test!($strict, assert_eq!(super::strict_mod_exp(a, &b, &m), result));
                    let a = U256::from(a_val);
                    crate::maybe_test!($constrained, assert_eq!(super::constrained_mod_exp(a, &b, &m), result));
                    let a = U256::from(a_val);
                    crate::maybe_test!($basic, assert_eq!(super::basic_mod_exp(a, b, m), result));
                }
            }
        }
    };
}

#[cfg(test)]
mod bnum_exp_tests {
    use super::basic_mod_exp;
    use super::constrained_mod_exp;
    use super::strict_mod_exp;

    //     exp_test_module!(
    //         bnum,
    //         bnum::types::U256,
    //         strict: off, // OverflowingAdd + OverflowingSub is not implemented
    //         constrained: on,
    //         basic: on,
    //     );

    //     exp_test_module!(
    //         bnum_patched,
    //         bnum_patched::types::U256,
    //         strict: on,
    //         constrained: on,
    //         basic: on,
    //     );

    //     exp_test_module!(
    //         crypto_bigint,
    //         crypto_bigint::U256,
    //         strict: off, // OverflowingAdd missing
    //         constrained: off, // RemAssign
    //         basic: off, // RemAssign is not implemented
    //     );

    //     exp_test_module!(
    //         crypto_bigint_patched,
    //         crypto_bigint_patched::U256,
    //         strict: on,
    //         constrained: on,
    //         basic: on,
    //     );

    //     exp_test_module!(
    //         num_bigint,
    //         num_bigint::BigUint,
    //         type U256 = num_bigint::BigUint;
    //         strict: off, // OverflowingAdd missing
    //         constrained: off, // WrappingAdd missing
    //         basic: off, // Copy cannot be implemented, heap allocation
    //     );

    //     exp_test_module!(
    //         num_bigint_patched,
    //         num_bigint_patched::BigUint,
    //         type U256 = num_bigint_patched::BigUint;
    //         strict: on,
    //         constrained: on,
    //         basic: off, // Copy cannot be implemented, heap allocation
    //     );

    //     exp_test_module!(
    //         ibig,
    //         ibig::UBig,
    //         type U256 = ibig::UBig;
    //         strict: off, // OverflowingAdd missing
    //         constrained: off, // WrappingAdd missing
    //         basic: off, // Copy cannot be implemented, heap allocation
    //     );

    //     exp_test_module!(
    //         ibig_patched,
    //         ibig_patched::UBig,
    //         type U256 = ibig_patched::UBig;
    //         strict: on,
    //         constrained: on,
    //         basic: off, // Copy cannot be implemented, heap allocation
    //     );

    // Default (Nct-personality) FixedUInt provides Rem; the wrapper
    // functions are usable here. The Ct personality intentionally omits
    // Rem (variable-time on operand magnitudes).
    exp_test_module!(
        fixed_bigint,
        fixed_bigint::FixedUInt,
        type U256 = fixed_bigint::FixedUInt<u8, 4>;
        strict: on,
        constrained: on,
        basic: on,
    );
}

#[cfg(test)]
mod fixed_bigint_pr_tests {
    use super::{basic_mod_exp_pr, constrained_mod_exp_pr, strict_mod_exp_pr};
    type U256 = fixed_bigint::FixedUInt<u8, 4>;

    #[test]
    fn test_mod_exp_basic_pr() {
        // 5^3 mod 13 = 125 mod 13 = 8
        let base = U256::from(5u8);
        let exp = U256::from(3u8);
        let m = U256::from(13u8);
        let expected = U256::from(8u8);

        assert_eq!(strict_mod_exp_pr(base, &exp, &m), expected);
        let base = U256::from(5u8);
        assert_eq!(constrained_mod_exp_pr(base, &exp, &m), expected);
        let base = U256::from(5u8);
        assert_eq!(basic_mod_exp_pr(base, exp, m), expected);
    }

    #[test]
    fn test_mod_exp_zero_exponent_pr() {
        // x^0 mod m = 1 (for m > 1)
        let base = U256::from(7u8);
        let exp = U256::from(0u8);
        let m = U256::from(13u8);
        let expected = U256::from(1u8);

        assert_eq!(strict_mod_exp_pr(base, &exp, &m), expected);
        let base = U256::from(7u8);
        assert_eq!(constrained_mod_exp_pr(base, &exp, &m), expected);
        let base = U256::from(7u8);
        assert_eq!(basic_mod_exp_pr(base, exp, m), expected);
    }

    /// Regression: every value mod 1 is 0, including 1. The square-and-multiply
    /// loop starts with `result = T::one()` and used to return 1 here.
    #[test]
    fn test_mod_exp_modulus_one_pr() {
        let m = U256::from(1u8);
        let zero = U256::from(0u8);
        // Exercise a representative grid of (base, exponent) pairs.
        let bases = [0u8, 1, 2, 7, 42, 255];
        let exps = [0u8, 1, 2, 5, 100];
        for &b in &bases {
            for &e in &exps {
                let base = U256::from(b);
                let exp = U256::from(e);
                assert_eq!(strict_mod_exp_pr(base, &exp, &m), zero);
                let base = U256::from(b);
                assert_eq!(constrained_mod_exp_pr(base, &exp, &m), zero);
                let base = U256::from(b);
                assert_eq!(basic_mod_exp_pr(base, exp, m), zero);
            }
        }
    }
}

#[cfg(test)]
mod nz_tests {
    use super::*;
    use const_num_traits::HasNonZero;

    #[test]
    fn basic_mod_exp_nz_matches_basic_mod_exp() {
        let m: u32 = 97;
        let m_nz = m.into_nonzero().unwrap();
        for base in [0u32, 1, 2, 96, 200] {
            for exp in [0u32, 1, 5, 96] {
                assert_eq!(
                    basic_mod_exp_nz(base, exp, m_nz),
                    basic_mod_exp(base, exp, m)
                );
            }
        }
    }

    #[test]
    fn basic_mod_exp_nz_modulus_one_returns_zero() {
        // `T::NonZero` rules out modulus == 0 but not modulus == 1; the
        // early-return preserves the `x mod 1 == 0` contract.
        let m_nz = 1u32.into_nonzero().unwrap();
        assert_eq!(basic_mod_exp_nz(123u32, 7u32, m_nz), 0);
    }

    #[test]
    fn constrained_mod_exp_nz_matches_constrained_mod_exp() {
        let m: u32 = 97;
        let m_nz = m.into_nonzero().unwrap();
        for base in [0u32, 1, 2, 96, 200] {
            for exp in [0u32, 1, 5, 96] {
                assert_eq!(
                    constrained_mod_exp_nz(base, &exp, m_nz),
                    constrained_mod_exp(base, &exp, &m)
                );
            }
        }
    }

    #[test]
    fn strict_mod_exp_nz_matches_strict_mod_exp() {
        let m: u32 = 97;
        let m_nz = m.into_nonzero().unwrap();
        for base in [0u32, 1, 2, 96, 200] {
            for exp in [0u32, 1, 5, 96] {
                assert_eq!(
                    strict_mod_exp_nz(base, &exp, m_nz),
                    strict_mod_exp(base, &exp, &m)
                );
            }
        }
    }
}

kaidokert / modmath-rs / 28725835473

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous