clock_curve_math/extensible/

generic_field.rs

//! Generic field arithmetic implementation.
//!
//! This module provides generic field elements and operations that can work
//! with different field parameters and moduli.

use super::field_parameters::FieldParameters;
use crate::bigint::BigInt;
use crate::error::MathError;

/// Generic field element with extensible parameters.
///
/// This struct provides a generic field element that can work with
/// different moduli and limb configurations through the FieldParameters trait.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct GenericFieldElement<P: FieldParameters> {
    /// The Montgomery representation of the field element
    value: BigInt,
    /// Phantom data to tie the element to its parameters
    _params: core::marker::PhantomData<P>,
}

#[allow(dead_code)]
impl<P: FieldParameters> GenericFieldElement<P> {
    /// Create a new field element from a BigInt.
    ///
    /// The value is automatically converted to Montgomery form.
    pub fn new(value: BigInt) -> Result<Self, MathError> {
        // Validate the value is in range
        if value.ct_cmp(&P::modulus()) != core::cmp::Ordering::Less {
            return Err(MathError::InvalidInput);
        }

        // For simplicity in the extensible implementation, store values directly
        // Full Montgomery optimization can be added later
        Ok(Self {
            value,
            _params: core::marker::PhantomData,
        })
    }

    /// Create a field element from raw Montgomery representation.
    ///
    /// This is unsafe because it doesn't validate the input.
    pub unsafe fn from_montgomery_unchecked(value: BigInt) -> Self {
        Self {
            value,
            _params: core::marker::PhantomData,
        }
    }

    /// Create a field element from raw Montgomery representation with validation.
    ///
    /// This validates that the input is in the correct range [0, modulus).
    pub fn from_montgomery_checked(value: BigInt) -> Result<Self, MathError> {
        let modulus = P::modulus();
        if value.ct_cmp(&BigInt::from_u64(0)) == core::cmp::Ordering::Less
            || value.ct_cmp(&modulus) != core::cmp::Ordering::Less
        {
            return Err(MathError::InvalidFieldElement);
        }
        Ok(Self {
            value,
            _params: core::marker::PhantomData,
        })
    }

    /// Get the Montgomery representation of this field element.
    ///
    /// Returns a reference to the internal Montgomery-form value.
    /// Note: In this extensible implementation, values are stored directly
    /// rather than in full Montgomery form for simplicity.
    pub fn to_montgomery(&self) -> &BigInt {
        &self.value
    }

    /// Convert this field element to regular (non-Montgomery) representation.
    ///
    /// Returns the field element value in standard form, not Montgomery form.
    /// In this extensible implementation, values are stored directly,
    /// so this simply returns a clone of the internal value.
    pub fn to_regular(&self) -> BigInt {
        // For simplicity, values are stored directly
        self.value.clone()
    }

    /// Get the modulus for this field.
    ///
    /// Returns the prime modulus that defines this finite field.
    /// This is a static method that delegates to the FieldParameters trait.
    pub fn modulus() -> BigInt {
        P::modulus()
    }

    /// Convert a value to Montgomery form (static version for extensible arithmetic).
    ///
    /// This function converts a regular integer value to its Montgomery representation.
    /// The conversion is done using: value * R mod N = montgomery_mul(value, R²)
    ///
    /// # Arguments
    /// * `value` - The value to convert to Montgomery form
    /// * `modulus` - The field modulus N
    /// * `r` - The Montgomery radix R (typically a power of 2)
    /// * `r2` - R² mod N, the Montgomery constant
    /// * `n_prime` - The Montgomery inverse of N modulo R
    ///
    /// # Returns
    /// The value converted to Montgomery form
    fn to_montgomery_static(
        value: &BigInt,
        modulus: &BigInt,
        r: &BigInt,
        r2: &BigInt,
        n_prime: &BigInt,
    ) -> BigInt {
        // value * R mod N = montgomery_mul(value, R²)
        Self::montgomery_mul_static(value, r2, modulus, r, n_prime)
    }

    /// Convert a value from Montgomery form to regular representation (static version).
    ///
    /// This function performs Montgomery reduction to convert a Montgomery-form
    /// value back to its regular integer representation.
    ///
    /// # Arguments
    /// * `value` - The Montgomery-form value to convert
    /// * `modulus` - The field modulus N
    /// * `r` - The Montgomery radix R (typically a power of 2)
    /// * `n_prime` - The Montgomery inverse of N modulo R
    ///
    /// # Returns
    /// The value converted from Montgomery form to regular representation
    fn from_montgomery_static(
        value: &BigInt,
        modulus: &BigInt,
        r: &BigInt,
        n_prime: &BigInt,
    ) -> BigInt {
        // Montgomery reduction
        let m = value.mul(n_prime).div_rem(r).1;
        let u = value.add(&m.mul(modulus)).div_rem(r).1;

        if u.ct_cmp(modulus) != core::cmp::Ordering::Less {
            u.sub(modulus)
        } else {
            u
        }
    }

    /// Perform Montgomery multiplication (static version for extensible arithmetic).
    ///
    /// Computes (a * b * R^(-1)) mod N using the Montgomery multiplication algorithm.
    /// This is more efficient than regular modular multiplication for multiple operations.
    ///
    /// # Arguments
    /// * `a` - First operand (in Montgomery form)
    /// * `b` - Second operand (in Montgomery form)
    /// * `modulus` - The field modulus N
    /// * `r` - The Montgomery radix R (typically a power of 2)
    /// * `n_prime` - The Montgomery inverse of N modulo R
    ///
    /// # Returns
    /// The product (a * b * R^(-1)) mod N in Montgomery form
    #[allow(clippy::many_single_char_names)]
    fn montgomery_mul_static(
        a: &BigInt,
        b: &BigInt,
        modulus: &BigInt,
        r: &BigInt,
        n_prime: &BigInt,
    ) -> BigInt {
        let t = a.mul(b);
        let m = t.mul(n_prime).div_rem(r).1;
        let u = t.add(&m.mul(modulus)).div_rem(r).1;

        if u.ct_cmp(modulus) != core::cmp::Ordering::Less {
            u.sub(modulus)
        } else {
            u
        }
    }

    /// Perform Montgomery squaring (static version for extensible arithmetic).
    ///
    /// Computes (a * a * R^(-1)) mod N using the Montgomery multiplication algorithm.
    /// This is optimized for squaring operations, which are common in cryptographic computations.
    ///
    /// # Arguments
    /// * `a` - The operand to square (in Montgomery form)
    /// * `modulus` - The field modulus N
    /// * `r` - The Montgomery radix R (typically a power of 2)
    /// * `n_prime` - The Montgomery inverse of N modulo R
    ///
    /// # Returns
    /// The square (a * a * R^(-1)) mod N in Montgomery form
    fn montgomery_square_static(
        a: &BigInt,
        modulus: &BigInt,
        r: &BigInt,
        n_prime: &BigInt,
    ) -> BigInt {
        Self::montgomery_mul_static(a, a, modulus, r, n_prime)
    }

    /// Perform Montgomery reduction (static version for extensible arithmetic).
    ///
    /// Reduces a value t modulo N using the Montgomery reduction algorithm.
    /// This converts a value from the range [0, N*R) to [0, N) by computing (t * R^(-1)) mod N.
    ///
    /// # Arguments
    /// * `t` - The value to reduce (typically a product in the range [0, N*R))
    /// * `modulus` - The field modulus N
    /// * `r` - The Montgomery radix R (typically a power of 2)
    /// * `n_prime` - The Montgomery inverse of N modulo R
    ///
    /// # Returns
    /// The reduced value (t * R^(-1)) mod N
    fn montgomery_reduce_static(
        t: &BigInt,
        modulus: &BigInt,
        r: &BigInt,
        n_prime: &BigInt,
    ) -> BigInt {
        let m = t.mul(n_prime).div_rem(r).1;
        let u = t.add(&m.mul(modulus)).div_rem(r).1;

        if u.ct_cmp(modulus) != core::cmp::Ordering::Less {
            u.sub(modulus)
        } else {
            u
        }
    }
}

/// Generic field arithmetic operations.
///
/// This trait defines the core arithmetic operations that can be performed
/// on field elements in a finite field. All operations are performed modulo
/// the field's prime modulus, ensuring results remain within the field.
pub trait GenericFieldOps<P: FieldParameters> {
    /// Add two field elements.
    ///
    /// Computes (self + rhs) mod modulus. The result is always a valid
    /// field element in the range [0, modulus).
    fn add(&self, rhs: &GenericFieldElement<P>) -> GenericFieldElement<P>;

    /// Subtract two field elements.
    ///
    /// Computes (self - rhs) mod modulus. If the result would be negative,
    /// the modulus is added to ensure the result is in [0, modulus).
    fn sub(&self, rhs: &GenericFieldElement<P>) -> GenericFieldElement<P>;

    /// Multiply two field elements.
    ///
    /// Computes (self * rhs) mod modulus. The result is always a valid
    /// field element in the range [0, modulus).
    fn mul(&self, rhs: &GenericFieldElement<P>) -> GenericFieldElement<P>;

    /// Compute the multiplicative inverse.
    ///
    /// Finds the element x such that (self * x) ≡ 1 mod modulus.
    /// Returns an error if the element is zero (which has no inverse)
    /// or if the extended Euclidean algorithm fails.
    fn inv(&self) -> Result<GenericFieldElement<P>, MathError>;

    /// Compute the square of this field element.
    ///
    /// Computes (self * self) mod modulus. This is often more efficient
    /// than general multiplication and is commonly used in exponentiation algorithms.
    fn square(&self) -> GenericFieldElement<P>;

    /// Check equality in constant time.
    ///
    /// Performs a constant-time comparison to prevent timing attacks.
    /// Returns true if the two elements represent the same field value.
    fn ct_eq(&self, rhs: &GenericFieldElement<P>) -> bool;

    /// Check if this element is the additive identity (zero).
    ///
    /// Returns true if this element represents 0 in the field.
    fn is_zero(&self) -> bool;
}

impl<P: FieldParameters> GenericFieldOps<P> for GenericFieldElement<P> {
    /// Add two field elements.
    ///
    /// Performs modular addition: (self + rhs) mod modulus.
    /// If the sum exceeds the modulus, it wraps around by subtracting the modulus once.
    fn add(&self, rhs: &GenericFieldElement<P>) -> GenericFieldElement<P> {
        let sum = self.value.add(&rhs.value);
        let reduced = if sum.ct_cmp(&P::modulus()) != core::cmp::Ordering::Less {
            sum.sub(&P::modulus())
        } else {
            sum
        };

        // The result is reduced modulo the modulus, so it's valid
        Self::from_montgomery_checked(reduced)
            .expect("Montgomery reduction should produce valid field element")
    }

    /// Subtract two field elements.
    ///
    /// Performs modular subtraction: (self - rhs) mod modulus.
    /// If self < rhs, adds the modulus to the difference to ensure a positive result.
    fn sub(&self, rhs: &GenericFieldElement<P>) -> GenericFieldElement<P> {
        let diff = if self.value.ct_cmp(&rhs.value) != core::cmp::Ordering::Less {
            self.value.sub(&rhs.value)
        } else {
            // Add modulus to handle underflow
            let temp = self.value.add(&P::modulus());
            temp.sub(&rhs.value)
        };

        // The result is in [0, modulus), so it's valid
        Self::from_montgomery_checked(diff).unwrap()
    }

    fn mul(&self, rhs: &GenericFieldElement<P>) -> GenericFieldElement<P> {
        let product = self.value.mul(&rhs.value);
        let reduced = product.div_rem(&P::modulus()).1;

        // The result is reduced modulo the modulus, so it's valid
        Self::from_montgomery_checked(reduced)
            .expect("Montgomery reduction should produce valid field element")
    }

    /// Compute the multiplicative inverse using the extended Euclidean algorithm.
    ///
    /// Finds x such that (self * x) ≡ 1 mod modulus.
    /// Uses the extended Euclidean algorithm to compute the modular inverse.
    /// Returns DivisionByZero error if the element is zero or if no inverse exists.
    fn inv(&self) -> Result<GenericFieldElement<P>, MathError> {
        if self.is_zero() {
            return Err(MathError::DivisionByZero);
        }

        // For the extensible implementation, compute inverse using extended Euclidean algorithm
        // This is simpler and works for any modulus
        let modulus = P::modulus();
        let mut t = BigInt::from_u64(0);
        let mut new_t = BigInt::from_u64(1);
        let mut r = modulus.clone();
        let mut new_r = self.value.clone();

        while new_r.ct_cmp(&BigInt::from_u64(0)) != core::cmp::Ordering::Equal {
            let quotient = r.div_rem(&new_r).0;
            let temp_t = t.clone();
            t = new_t.clone();
            new_t = temp_t.sub(&quotient.mul(&new_t));

            let temp_r = r.clone();
            r = new_r.clone();
            new_r = temp_r.sub(&quotient.mul(&new_r));
        }

        if r.ct_cmp(&BigInt::from_u64(1)) != core::cmp::Ordering::Equal {
            return Err(MathError::DivisionByZero); // No inverse exists
        }

        // Make result positive
        if t.ct_cmp(&BigInt::from_u64(0)) == core::cmp::Ordering::Less {
            t = t.add(&modulus);
        }

        // The result is a valid field element in [0, modulus)
        Self::from_montgomery_checked(t)
    }

    /// Compute the square of this field element.
    ///
    /// Performs modular squaring: (self * self) mod modulus.
    /// More efficient than general multiplication for exponentiation algorithms.
    fn square(&self) -> GenericFieldElement<P> {
        let squared = self.value.mul(&self.value);
        let reduced = squared.div_rem(&P::modulus()).1;

        // The result is reduced modulo the modulus, so it's valid
        Self::from_montgomery_checked(reduced)
            .expect("Montgomery reduction should produce valid field element")
    }

    /// Check equality in constant time.
    ///
    /// Performs a constant-time comparison of the underlying BigInt values
    /// to prevent timing-based side-channel attacks.
    fn ct_eq(&self, rhs: &GenericFieldElement<P>) -> bool {
        // For BigInt comparison, we need to convert to bytes or use the cmp method
        // This is a simplified version for now
        self.value.ct_cmp(&rhs.value) == core::cmp::Ordering::Equal
    }

    /// Check if this element is the additive identity (zero).
    ///
    /// Returns true if this field element represents 0 in the finite field.
    /// Converts to regular representation and compares with zero.
    fn is_zero(&self) -> bool {
        // Check if the regular representation is zero
        self.to_regular().ct_cmp(&BigInt::from_u64(0)) == core::cmp::Ordering::Equal
    }
}