clock-curve-math 1.1.3

//! Comprehensive tests for multi-exponentiation operations.
//!
//! This module tests the multi-exponentiation algorithms used in
//! cryptographic protocols and zero-knowledge proofs.

use clock_curve_math::{BigInt, FieldElement, FieldOps, MathError, field::multi_exp::*};

#[cfg(feature = "alloc")]
mod multi_exp_basic_tests {
    use super::*;

    #[test]
    fn test_multi_exp_empty_inputs() {
        let bases: Vec<FieldElement> = vec![];
        let exponents: Vec<BigInt> = vec![];

        let result = multi_exp(&bases, &exponents).unwrap();
        assert_eq!(result, FieldElement::from_u64(1));
    }

    #[test]
    fn test_multi_exp_single_element() {
        let bases = vec![FieldElement::from_u64(2)];
        let exponents = vec![BigInt::from_u64(10)];

        let result = multi_exp(&bases, &exponents).unwrap();
        let expected = FieldElement::from_u64(2).pow(&BigInt::from_u64(10));
        assert_eq!(result, expected);
        assert_eq!(result, FieldElement::from_u64(1024)); // 2^10 = 1024
    }

    #[test]
    fn test_multi_exp_two_elements() {
        let bases = vec![FieldElement::from_u64(2), FieldElement::from_u64(3)];
        let exponents = vec![BigInt::from_u64(3), BigInt::from_u64(2)];

        let result = multi_exp(&bases, &exponents).unwrap();
        // Expected: 2^3 * 3^2 = 8 * 9 = 72
        let expected = FieldElement::from_u64(8).mul(&FieldElement::from_u64(9));
        assert_eq!(result, expected);
    }

    #[test]
    fn test_multi_exp_three_elements() {
        let bases = vec![
            FieldElement::from_u64(2),
            FieldElement::from_u64(3),
            FieldElement::from_u64(5),
        ];
        let exponents = vec![
            BigInt::from_u64(2),
            BigInt::from_u64(1),
            BigInt::from_u64(3),
        ];

        let result = multi_exp(&bases, &exponents).unwrap();
        // Expected: 2^2 * 3^1 * 5^3 = 4 * 3 * 125 = 1500
        let expected = FieldElement::from_u64(4)
            .mul(&FieldElement::from_u64(3))
            .mul(&FieldElement::from_u64(125));
        assert_eq!(result, expected);
    }

    #[test]
    fn test_multi_exp_large_exponents() {
        let bases = vec![FieldElement::from_u64(2)];
        let exponents = vec![BigInt::from_u64(100)];

        let result = multi_exp(&bases, &exponents).unwrap();
        let expected = FieldElement::from_u64(2).pow(&BigInt::from_u64(100));
        assert_eq!(result, expected);
    }

    #[test]
    fn test_multi_exp_zero_exponents() {
        let bases = vec![
            FieldElement::from_u64(2),
            FieldElement::from_u64(3),
            FieldElement::from_u64(5),
        ];
        let exponents = vec![
            BigInt::from_u64(0),
            BigInt::from_u64(0),
            BigInt::from_u64(0),
        ];

        let result = multi_exp(&bases, &exponents).unwrap();
        // Any base^0 = 1, product of 1s = 1
        assert_eq!(result, FieldElement::from_u64(1));
    }

    #[test]
    fn test_multi_exp_mixed_zero_and_nonzero() {
        let bases = vec![
            FieldElement::from_u64(2),
            FieldElement::from_u64(3),
            FieldElement::from_u64(5),
        ];
        let exponents = vec![
            BigInt::from_u64(2), // 2^2 = 4
            BigInt::from_u64(0), // 3^0 = 1
            BigInt::from_u64(1), // 5^1 = 5
        ];

        let result = multi_exp(&bases, &exponents).unwrap();
        // Expected: 4 * 1 * 5 = 20
        assert_eq!(result, FieldElement::from_u64(20));
    }

    #[test]
    fn test_multi_exp_mismatched_lengths() {
        let bases = vec![FieldElement::from_u64(2)];
        let exponents = vec![BigInt::from_u64(1), BigInt::from_u64(2)];

        assert!(multi_exp(&bases, &exponents).is_none());
    }

    #[test]
    fn test_multi_exp_null_arrays() {
        let bases = vec![FieldElement::from_u64(2), FieldElement::from_u64(3)];
        let exponents = vec![BigInt::from_u64(1)];

        assert!(multi_exp(&bases, &exponents).is_none());
    }
}

#[cfg(feature = "alloc")]
mod multi_exp_checked_tests {
    use super::*;

    #[test]
    fn test_multi_exp_checked_valid_inputs() {
        let bases = vec![FieldElement::from_u64(2), FieldElement::from_u64(3)];
        let exponents = vec![BigInt::from_u64(3), BigInt::from_u64(2)];

        let result = multi_exp_checked(&bases, &exponents).unwrap();
        let expected = FieldElement::from_u64(8).mul(&FieldElement::from_u64(9));
        assert_eq!(result, expected);
    }

    #[test]
    fn test_multi_exp_checked_empty_inputs() {
        let bases: Vec<FieldElement> = vec![];
        let exponents: Vec<BigInt> = vec![];

        let result = multi_exp_checked(&bases, &exponents).unwrap();
        assert_eq!(result, FieldElement::from_u64(1));
    }

    #[test]
    fn test_multi_exp_checked_mismatched_lengths() {
        let bases = vec![FieldElement::from_u64(2)];
        let exponents = vec![BigInt::from_u64(1), BigInt::from_u64(2)];

        let result = multi_exp_checked(&bases, &exponents);
        assert!(result.is_err());
        assert_eq!(result.unwrap_err(), MathError::InvalidInput);
    }
}

#[cfg(feature = "alloc")]
mod multi_exp_correctness_tests {
    use super::*;

    #[test]
    fn test_multi_exp_correctness_comprehensive() {
        // Test various combinations to ensure correctness
        let test_cases = vec![
            // (bases, exponents, expected_result)
            (
                vec![FieldElement::from_u64(2)],
                vec![BigInt::from_u64(0)],
                FieldElement::from_u64(1), // 2^0 = 1
            ),
            (
                vec![FieldElement::from_u64(2)],
                vec![BigInt::from_u64(1)],
                FieldElement::from_u64(2), // 2^1 = 2
            ),
            (
                vec![FieldElement::from_u64(3), FieldElement::from_u64(5)],
                vec![BigInt::from_u64(1), BigInt::from_u64(1)],
                FieldElement::from_u64(15), // 3^1 * 5^1 = 15
            ),
            (
                vec![FieldElement::from_u64(2), FieldElement::from_u64(2)],
                vec![BigInt::from_u64(2), BigInt::from_u64(3)],
                FieldElement::from_u64(4 * 8), // 2^2 * 2^3 = 4 * 8 = 32
            ),
        ];

        for (bases, exponents, expected) in test_cases {
            let result = multi_exp(&bases, &exponents).unwrap();
            assert_eq!(result, expected);
        }
    }

    #[test]
    fn test_multi_exp_vs_individual_computation() {
        // Test that multi_exp gives same result as individual computations
        let bases = vec![
            FieldElement::from_u64(2),
            FieldElement::from_u64(3),
            FieldElement::from_u64(5),
        ];
        let exponents = vec![
            BigInt::from_u64(2),
            BigInt::from_u64(3),
            BigInt::from_u64(1),
        ];

        let multi_result = multi_exp(&bases, &exponents).unwrap();

        // Compute individually
        let term1 = bases[0].pow(&exponents[0]);
        let term2 = bases[1].pow(&exponents[1]);
        let term3 = bases[2].pow(&exponents[2]);
        let individual_result = term1.mul(&term2).mul(&term3);

        assert_eq!(multi_result, individual_result);
    }

    #[test]
    fn test_multi_exp_mathematical_properties() {
        // Test commutative property: order of terms shouldn't matter
        let bases1 = vec![FieldElement::from_u64(2), FieldElement::from_u64(3)];
        let exponents1 = vec![BigInt::from_u64(2), BigInt::from_u64(3)];

        let bases2 = vec![FieldElement::from_u64(3), FieldElement::from_u64(2)];
        let exponents2 = vec![BigInt::from_u64(3), BigInt::from_u64(2)];

        let result1 = multi_exp(&bases1, &exponents1).unwrap();
        let result2 = multi_exp(&bases2, &exponents2).unwrap();

        // Both should give 2^2 * 3^3 = 4 * 27 = 108
        assert_eq!(result1, result2);
        assert_eq!(result1, FieldElement::from_u64(108));
    }

    #[test]
    fn test_multi_exp_associativity() {
        // Test that (a*b)*c = a*(b*c) for multi-exponentiation
        let bases = vec![
            FieldElement::from_u64(2),
            FieldElement::from_u64(3),
            FieldElement::from_u64(5),
        ];
        let exponents = vec![
            BigInt::from_u64(1),
            BigInt::from_u64(1),
            BigInt::from_u64(1),
        ];

        let result = multi_exp(&bases, &exponents).unwrap();

        // Should be 2 * 3 * 5 = 30
        assert_eq!(result, FieldElement::from_u64(30));
    }
}

#[cfg(feature = "alloc")]
mod multi_exp_performance_tests {
    use super::*;

    #[test]
    fn test_multi_exp_various_sizes() {
        // Test with different numbers of terms
        for n in 1..=10 {
            let bases: Vec<FieldElement> = (0..n).map(|i| FieldElement::from_u64(i + 2)).collect();
            let exponents: Vec<BigInt> = (0..n).map(|i| BigInt::from_u64(i + 1)).collect();

            let result = multi_exp(&bases, &exponents);
            assert!(result.is_some(), "Failed for n = {}", n);
        }
    }

    #[test]
    fn test_multi_exp_large_exponents() {
        // Test with large exponents
        let bases = vec![FieldElement::from_u64(2), FieldElement::from_u64(3)];
        let large_exp = BigInt::from_limbs(&[u64::MAX, u64::MAX, 0, 0]);
        let exponents = vec![large_exp.clone(), large_exp];

        let result = multi_exp(&bases, &exponents);
        assert!(result.is_some());
    }

    #[test]
    fn test_multi_exp_bit_length_handling() {
        // Test with varying bit lengths
        let bases = vec![
            FieldElement::from_u64(2),
            FieldElement::from_u64(3),
            FieldElement::from_u64(5),
        ];

        // Small exponent
        let small_exp = vec![BigInt::from_u64(1); 3];
        let result_small = multi_exp(&bases, &small_exp).unwrap();

        // Large exponent
        let large_exp = vec![BigInt::from_u64(100); 3];
        let result_large = multi_exp(&bases, &large_exp).unwrap();

        // Results should be different
        assert_ne!(result_small, result_large);
    }
}

#[cfg(feature = "alloc")]
mod multi_exp_algorithm_tests {
    use super::*;

    #[test]
    fn test_multi_exp_algorithm_correctness() {
        // Test the core algorithm logic
        let bases = vec![FieldElement::from_u64(2)];
        let exponents = vec![BigInt::from_u64(3)]; // 2^3 = 8

        let result = multi_exp(&bases, &exponents).unwrap();
        assert_eq!(result, FieldElement::from_u64(8));
    }

    #[test]
    fn test_multi_exp_max_bit_length_calculation() {
        // Test that max bit length is calculated correctly
        let bases = vec![FieldElement::from_u64(2), FieldElement::from_u64(3)];
        let exponents = vec![
            BigInt::from_u64(1),    // 1 bit
            BigInt::from_u64(1024), // 11 bits
        ];

        let result = multi_exp(&bases, &exponents).unwrap();
        // Should be 2^1 * 3^1024
        let expected = FieldElement::from_u64(2)
            .pow(&BigInt::from_u64(1))
            .mul(&FieldElement::from_u64(3).pow(&BigInt::from_u64(1024)));
        assert_eq!(result, expected);
    }

    #[test]
    fn test_multi_exp_bit_processing() {
        // Test specific bit processing
        let bases = vec![FieldElement::from_u64(2)];
        let exponents = vec![BigInt::from_u64(5)]; // 101 in binary

        let result = multi_exp(&bases, &exponents).unwrap();
        assert_eq!(result, FieldElement::from_u64(32)); // 2^5 = 32
    }
}

#[cfg(feature = "alloc")]
mod multi_exp_consistency_tests {
    use super::*;

    #[test]
    fn test_multi_exp_consistency_with_naive() {
        // Test that multi_exp gives same results as naive computation
        for n in 1usize..=5 {
            let bases: Vec<FieldElement> = (0..n)
                .map(|i| FieldElement::from_u64(i as u64 + 2))
                .collect();
            let exponents: Vec<BigInt> = (0..n)
                .map(|i| BigInt::from_u64((i as u64) % 4 + 1))
                .collect();

            let multi_result = multi_exp(&bases, &exponents).unwrap();

            // Compute naive result
            let mut naive_result = FieldElement::from_u64(1);
            for i in 0..n {
                let i_usize = i as usize;
                let term = bases[i_usize].pow(&exponents[i_usize]);
                naive_result = naive_result.mul(&term);
            }

            assert_eq!(multi_result, naive_result, "Failed for n = {}", n);
        }
    }

    #[test]
    fn test_multi_exp_deterministic() {
        // Test that results are deterministic
        let bases = vec![FieldElement::from_u64(2), FieldElement::from_u64(3)];
        let exponents = vec![BigInt::from_u64(5), BigInt::from_u64(3)];

        let result1 = multi_exp(&bases, &exponents).unwrap();
        let result2 = multi_exp(&bases, &exponents).unwrap();

        assert_eq!(result1, result2);
    }
}

#[cfg(feature = "alloc")]
mod multi_exp_edge_cases {
    use super::*;

    #[test]
    fn test_multi_exp_max_elements() {
        // Test with maximum reasonable number of elements
        let n = 50;
        let bases: Vec<FieldElement> = (0..n)
            .map(|i| FieldElement::from_u64((i % 10) + 2))
            .collect();
        let exponents: Vec<BigInt> = (0..n).map(|_| BigInt::from_u64(2)).collect();

        let result = multi_exp(&bases, &exponents);
        assert!(result.is_some());
    }

    #[test]
    fn test_multi_exp_duplicate_bases() {
        // Test with duplicate bases
        let bases = vec![
            FieldElement::from_u64(2),
            FieldElement::from_u64(2),
            FieldElement::from_u64(2),
        ];
        let exponents = vec![
            BigInt::from_u64(1),
            BigInt::from_u64(2),
            BigInt::from_u64(3),
        ];

        let result = multi_exp(&bases, &exponents).unwrap();
        // Should be 2^1 * 2^2 * 2^3 = 2^(1+2+3) = 2^6 = 64
        assert_eq!(result, FieldElement::from_u64(64));
    }

    #[test]
    fn test_multi_exp_identity_elements() {
        // Test with identity elements (base = 1)
        let bases = vec![
            FieldElement::from_u64(1), // 1^anything = 1
            FieldElement::from_u64(2),
            FieldElement::from_u64(1), // 1^anything = 1
        ];
        let exponents = vec![
            BigInt::from_u64(100),
            BigInt::from_u64(3),
            BigInt::from_u64(50),
        ];

        let result = multi_exp(&bases, &exponents).unwrap();
        // Should be 1 * 2^3 * 1 = 8
        assert_eq!(result, FieldElement::from_u64(8));
    }
}