clock_curve_math/extensible/

multiplication.rs

//! Advanced multiplication algorithms for extensible arithmetic.
//!
//! This module provides various multiplication algorithms optimized for
//! different operand sizes and computational requirements.

use crate::bigint::BigInt;

/// Multiplication algorithms for multi-limb arithmetic.
///
/// This enum defines different algorithms for multiplying large multi-precision
/// integers (BigInt). Each algorithm offers different trade-offs between
/// performance, memory usage, and complexity. The choice of algorithm depends
/// on the size of the operands and the computational requirements.
///
/// # Performance Characteristics
/// - **Standard/Schoolbook**: O(n²) - Simple, good for small numbers
/// - **Karatsuba**: O(n^1.585) - Good balance for medium-sized numbers
/// - **Toom-Cook**: O(n^1.465) - Better for large numbers, more complex
/// - **FFT**: O(n log n) - Optimal for very large numbers, highest overhead
///
/// # Memory Usage
/// Different algorithms have different memory requirements and may allocate
/// temporary BigInt values during computation.
///
/// # Algorithm Selection
/// The library automatically selects appropriate algorithms based on operand
/// sizes, but this enum allows manual override for specific use cases.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum MultiplicationAlgorithm {
    /// Standard long multiplication (schoolbook algorithm).
    ///
    /// This is the traditional "grade school" multiplication method that
    /// multiplies each digit of one number by each digit of the other.
    /// Simple to implement and optimal for small numbers.
    ///
    /// **Complexity**: O(n²)
    /// **Memory**: O(1) additional space
    /// **Best for**: Numbers with < 1000 bits
    Standard,

    /// Alias for Standard multiplication algorithm.
    ///
    /// Provided for clarity and compatibility. Same performance
    /// characteristics as Standard.
    Schoolbook,

    /// Karatsuba multiplication algorithm.
    ///
    /// Reduces the multiplication of two n-digit numbers to three
    /// multiplications of n/2-digit numbers using the identity:
    /// (a₁·2^(n/2) + a₀) · (b₁·2^(n/2) + b₀) =
    /// a₁b₁·2^n + (a₁b₁ + a₀b₀ - (a₀+a₁)(b₀+b₁))·2^(n/2) + a₀b₀
    ///
    /// **Complexity**: O(n^1.585)
    /// **Memory**: O(n) additional space
    /// **Best for**: Numbers with 1000-10000 bits
    Karatsuba,

    /// Toom-Cook multiplication algorithm (Toom-3 variant).
    ///
    /// Generalizes Karatsuba by splitting numbers into more parts and
    /// evaluating at multiple points. Uses polynomial interpolation to
    /// reconstruct the result. This implementation uses a simplified
    /// 3-way split with evaluation at points 0, 1, -1, 2, and ∞.
    ///
    /// **Complexity**: O(n^1.465)
    /// **Memory**: O(n) additional space
    /// **Best for**: Numbers with 10000-50000 bits
    ToomCook,

    /// Fast Fourier Transform (FFT) based multiplication.
    ///
    /// Uses FFT to multiply large numbers by converting them to the
    /// frequency domain. Requires the numbers to be treated as
    /// coefficients of polynomials. Most efficient asymptotically but
    /// has high constant factors and memory requirements.
    ///
    /// **Complexity**: O(n log n)
    /// **Memory**: O(n) additional space
    /// **Best for**: Numbers with >50000 bits
    /// **Note**: May fall back to Toom-Cook for smaller sizes due to overhead
    FFT,
}

/// Standalone Karatsuba multiplication implementation for BigInt.
///
/// Performs multiplication using the Karatsuba algorithm, which reduces
/// the multiplication of two n-digit numbers to three multiplications of
/// n/2-digit numbers. This provides better asymptotic performance than
/// standard long multiplication for large operands.
///
/// The algorithm splits each operand into high and low parts, then computes:
/// - z₀ = a_low × b_low
/// - z₂ = a_high × b_high
/// - z₁ = (a_low + a_high) × (b_low + b_high) - z₀ - z₂
///
/// The final result is: result = z₂ × 2^(2×half) + z₁ × 2^half + z₀
///
/// # Arguments
/// * `a` - First operand
/// * `b` - Second operand
///
/// # Returns
/// The product `a × b` computed using Karatsuba multiplication
///
/// # Performance
/// Falls back to standard multiplication for small operands (< 64 bits).
/// For larger operands, provides O(n^1.585) complexity vs O(n²) for schoolbook.
pub fn mul_karatsuba_standalone(a: &BigInt, b: &BigInt) -> BigInt {
    // Base case: small numbers use standard multiplication
    // Use a higher threshold to prevent excessive recursion
    if a.bit_length() < 192 || b.bit_length() < 192 {
        return a.mul(b);
    }

    // Split at 128-bit boundary (2 limbs) for simplicity and correctness
    // This ensures we're working with clean limb boundaries
    let half_limbs = 2; // 128 bits
    let half_bits = half_limbs * 64;

    // Create masks for the split
    // Low part: bottom 128 bits
    let low_mask = BigInt::from_limbs(&[u64::MAX, u64::MAX, 0, 0]);
    // High part: shift right by 128 bits
    let a_low = a.and(&low_mask);
    let a_high = a.shr(half_bits);
    let b_low = b.and(&low_mask);
    let b_high = b.shr(half_bits);

    // Compute the three products using Karatsuba's algorithm
    let z0 = mul_karatsuba_standalone(&a_low, &b_low);
    let z2 = mul_karatsuba_standalone(&a_high, &b_high);
    let z1 = mul_karatsuba_standalone(&(a_low.add(&a_high)), &(b_low.add(&b_high)));

    // z1 = (a_low + a_high) * (b_low + b_high) - z0 - z2
    let z1 = z1.sub(&z0).sub(&z2);

    // Combine results: result = z2 * 2^(2*half_bits) + z1 * 2^half_bits + z0
    let result = z2.shl(2 * half_bits).add(&z1.shl(half_bits)).add(&z0);

    result
}

/// Standalone Toom-Cook multiplication implementation for BigInt.
///
/// Performs multiplication using a simplified Toom-3 algorithm, which splits
/// numbers into three parts and evaluates polynomial multiplication at
/// specific points (0, 1, -1, 2, ∞) for interpolation.
///
/// The algorithm:
/// 1. Splits operands into three equal parts: a = a₂·2^(2s) + a₁·2^s + a₀
/// 2. Evaluates products at evaluation points
/// 3. Uses polynomial interpolation to reconstruct coefficients
/// 4. Combines results with appropriate shifts
///
/// # Arguments
/// * `a` - First operand
/// * `b` - Second operand
///
/// # Returns
/// The product `a × b` computed using Toom-Cook multiplication
///
/// # Performance
/// Falls back to Karatsuba multiplication for small operands (< 256 bits).
/// For larger operands, provides O(n^1.465) complexity.
/// Uses simplified interpolation - full Toom-Cook would be more accurate but complex.
pub fn mul_toom_cook_standalone(a: &BigInt, b: &BigInt) -> BigInt {
    // Base case: fallback to Karatsuba for smaller numbers
    if a.bit_length() < 256 || b.bit_length() < 256 {
        return mul_karatsuba_standalone(a, b);
    }

    // For this implementation, we'll use a simplified Toom-3 algorithm
    // Split numbers into 3 parts
    let n = core::cmp::max(a.bit_length(), b.bit_length());
    let part_size = (n + 2) / 3;

    let mask1 = (BigInt::from_u64(1) << part_size) - BigInt::from_u64(1);

    // Split a into a0, a1, a2
    let a0 = a.and(&mask1);
    let a1 = a.shr(part_size).and(&mask1);
    let a2 = a.shr(2 * part_size);

    // Split b into b0, b1, b2
    let b0 = b.and(&mask1);
    let b1 = b.shr(part_size).and(&mask1);
    let b2 = b.shr(2 * part_size);

    // Evaluate at points 0, 1, -1, 2, infinity
    let p0 = mul_karatsuba_standalone(&a0, &b0);
    let p1 = mul_karatsuba_standalone(&a0.add(&a1).add(&a2), &b0.add(&b1).add(&b2));
    let p_minus1 = mul_karatsuba_standalone(&a0.sub(&a1).add(&a2), &b0.sub(&b1).add(&b2));
    let p2 = mul_karatsuba_standalone(
        &a0.add(&a1.shl(1)).add(&a2.shl(2)),
        &b0.add(&b1.shl(1)).add(&b2.shl(2)),
    );
    let p_inf = mul_karatsuba_standalone(&a2, &b2);

    // Interpolate to get coefficients
    // This is a simplified interpolation - full Toom-Cook would be more complex
    let c4 = p_inf;
    let c3 = (p2.sub(&p_minus1)).div_rem(&BigInt::from_u64(3)).0;
    let c2 = (p1.sub(&p_minus1).shr(1)).sub(&p2.shr(2));
    let c1 = p_minus1.sub(&p0);
    let c0 = p0;

    // Combine results
    c4.shl(4 * part_size)
        .add(&c3.shl(3 * part_size))
        .add(&c2.shl(2 * part_size))
        .add(&c1.shl(part_size))
        .add(&c0)
}

/// Standalone FFT multiplication implementation for BigInt.
///
/// Performs multiplication using FFT-based algorithms for extremely large operands.
/// FFT multiplication provides asymptotically optimal O(n log n) complexity but
/// has high constant factors and memory requirements.
///
/// The implementation uses a configurable threshold (10,000 bits) above which
/// FFT multiplication is attempted. For smaller operands, it falls back to
/// Toom-Cook multiplication to avoid FFT overhead.
///
/// # Arguments
/// * `a` - First operand
/// * `b` - Second operand
///
/// # Returns
/// The product `a × b` computed using FFT-based multiplication
///
/// # Performance
/// Only beneficial for very large numbers (>10,000 bits). For cryptographic
/// applications, Toom-Cook multiplication usually provides sufficient performance.
/// Delegates to the FFT module's standalone implementation for actual computation.
pub fn mul_fft_standalone(a: &BigInt, b: &BigInt) -> BigInt {
    // FFT multiplication for extremely large operands
    // FFT provides O(n log n) complexity vs O(n^2) for schoolbook multiplication

    let a_bits = a.bit_length();
    let b_bits = b.bit_length();
    let max_bits = core::cmp::max(a_bits, b_bits);

    // Use FFT for large numbers, fall back to Toom-Cook for smaller ones
    // The threshold can be tuned based on performance characteristics
    const FFT_THRESHOLD_BITS: u32 = 10000; // Use FFT for numbers > 10,000 bits

    if max_bits < FFT_THRESHOLD_BITS {
        return mul_toom_cook_standalone(a, b);
    }

    // Use FFT for very large numbers
    // This provides asymptotically optimal multiplication performance
    crate::extensible::fft::mul_fft_standalone(a, b)
}

/// Implementation variant of Karatsuba multiplication.
///
/// This is an optimized implementation of the Karatsuba algorithm that uses
/// direct BigInt operations instead of recursive calls. It provides the same
/// mathematical algorithm as `mul_karatsuba_standalone` but with potentially
/// better performance for certain operand sizes.
///
/// Uses the Karatsuba identity to reduce multiplication complexity:
/// (a₁·2^(n/2) + a₀) · (b₁·2^(n/2) + b₀) =
/// a₁b₁·2^n + (a₁b₁ + a₀b₀ - (a₀+a₁)(b₀+b₁))·2^(n/2) + a₀b₀
///
/// # Arguments
/// * `a` - First operand
/// * `b` - Second operand
///
/// # Returns
/// The product `a × b` computed using the Karatsuba algorithm
///
/// # Performance
/// Uses standard multiplication for small operands (< 64 bits).
/// For larger operands, provides O(n^1.585) asymptotic complexity.
/// Avoids recursion overhead compared to the standalone version.
pub fn mul_karatsuba_impl(a: &BigInt, b: &BigInt) -> BigInt {
    // Base case: small numbers use standard multiplication
    if a.bit_length() < 64 || b.bit_length() < 64 {
        return a.mul(b);
    }

    // Split numbers into high and low parts
    let n = core::cmp::max(a.bit_length(), b.bit_length());
    let half = n / 2;

    // Create bit mask for splitting
    let mask = (BigInt::from_u64(1) << half) - BigInt::from_u64(1);

    // Split a: a = a_high * 2^half + a_low
    let a_low = a.and(&mask);
    let a_high = a.shr(half);

    // Split b: b = b_high * 2^half + b_low
    let b_low = b.and(&mask);
    let b_high = b.shr(half);

    // Compute the three products using Karatsuba's algorithm
    let z0 = a_low.mul(&b_low);
    let z2 = a_high.mul(&b_high);
    let z1 = (a_low.add(&a_high))
        .mul(&b_low.add(&b_high))
        .sub(&z0)
        .sub(&z2);

    // Combine results: result = z2 * 2^(2*half) + z1 * 2^half + z0
    z2.shl(2 * half).add(&z1.shl(half)).add(&z0)
}

/// Implementation variant of Toom-Cook multiplication.
///
/// This is an optimized implementation of the Toom-3 algorithm using direct
/// BigInt operations. It splits operands into three parts and uses polynomial
/// evaluation/interpolation for multiplication, providing better asymptotic
/// performance than Karatsuba for large operands.
///
/// The algorithm evaluates the product polynomial at points {0, 1, -1, 2, ∞}
/// and uses interpolation to recover the result coefficients. This implementation
/// uses simplified interpolation formulas for efficiency.
///
/// # Arguments
/// * `a` - First operand
/// * `b` - Second operand
///
/// # Returns
/// The product `a × b` computed using the Toom-3 algorithm
///
/// # Performance
/// Falls back to Karatsuba for small operands (< 256 bits).
/// For larger operands, provides O(n^1.465) asymptotic complexity.
/// Uses direct operations rather than recursive calls for better performance.
pub fn mul_toom_cook_impl(a: &BigInt, b: &BigInt) -> BigInt {
    // Base case: fallback to Karatsuba for smaller numbers
    if a.bit_length() < 256 || b.bit_length() < 256 {
        return mul_karatsuba_impl(a, b);
    }

    // For this implementation, we'll use a simplified Toom-3 algorithm
    // Split numbers into 3 parts
    let n = core::cmp::max(a.bit_length(), b.bit_length());
    let part_size = (n + 2) / 3;

    let mask1 = (BigInt::from_u64(1) << part_size) - BigInt::from_u64(1);

    // Split a into a0, a1, a2
    let a0 = a.and(&mask1);
    let a1 = a.shr(part_size).and(&mask1);
    let a2 = a.shr(2 * part_size);

    // Split b into b0, b1, b2
    let b0 = b.and(&mask1);
    let b1 = b.shr(part_size).and(&mask1);
    let b2 = b.shr(2 * part_size);

    // Evaluate at points 0, 1, -1, 2, infinity
    let p0 = a0.mul(&b0);
    let p1 = (a0.add(&a1).add(&a2)).mul(&b0.add(&b1).add(&b2));
    let p_minus1 = (a0.sub(&a1).add(&a2)).mul(&b0.sub(&b1).add(&b2));
    let p2 = (a0.add(&a1.shl(1)).add(&a2.shl(2))).mul(&b0.add(&b1.shl(1)).add(&b2.shl(2)));
    let p_inf = a2.mul(&b2);

    // Interpolate to get coefficients
    // This is a simplified interpolation - full Toom-Cook would be more complex
    let c4 = p_inf;
    let c3 = (p2.sub(&p_minus1)).div_rem(&BigInt::from_u64(3)).0;
    let c2 = (p1.sub(&p_minus1).shr(1)).sub(&p2.shr(2));
    let c1 = p_minus1.sub(&p0);
    let c0 = p0;

    // Combine results
    c4.shl(4 * part_size)
        .add(&c3.shl(3 * part_size))
        .add(&c2.shl(2 * part_size))
        .add(&c1.shl(part_size))
        .add(&c0)
}

/// Implementation variant of FFT-based multiplication.
///
/// This function provides FFT-based multiplication for extremely large operands.
/// It uses the FFT multiplier implementation from the fft module to achieve
/// O(n log n) asymptotic complexity for multiplication.
///
/// The FFT implementation requires the "std" feature for trigonometric functions
/// and memory allocation. Without std, it falls back to Toom-Cook multiplication.
///
/// # Arguments
/// * `a` - First operand
/// * `b` - Second operand
///
/// # Returns
/// The product `a × b` computed using FFT-based multiplication
///
/// # Performance
/// Uses FFT multiplication for large operands (>10,000 bits) when std feature
/// is enabled, providing O(n log n) complexity. Falls back to Toom-Cook for
/// smaller operands or when std is not available.
///
/// # Features
/// Requires the "std" feature for full FFT functionality. Without std,
/// falls back to Toom-Cook multiplication.
pub fn mul_fft_impl(a: &BigInt, b: &BigInt) -> BigInt {
    // Delegate to the FFT module's standalone implementation
    // This provides the actual FFT multiplication when std feature is available
    crate::extensible::fft::mul_fft_standalone(a, b)
}