hop-core 0.1.0

// Copyright (c) 2025 Lex Luger. All Rights Reserved.
// This software (HOP-CORE) is proprietary and confidential.
// Unauthorized copying, distribution, or use is strictly prohibited
// without explicit written permission from the author.
// Commercial licenses are available. Contact: lexluger.dev@proton.me
use core::fmt;
use core::ops::{Add, Sub, Mul};

/// Simple finite field arithmetic modulo a prime p (u64).
/// Uses u128 intermediates to avoid overflow on multiplication.
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct Field {
    pub v: u64,
}

impl fmt::Debug for Field {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "Field({})", self.v)
    }
}

impl Field {
    /// Set the prime modulus here. For prototype/testing you can change it.
    pub const MOD: u64 = 65537;

    /// Create element with reduction
    pub fn new(x: u128) -> Self {
        let m = Self::MOD as u128;
        Field { v: (x % m) as u64 }
    }

    pub fn zero() -> Self {
        Field { v: 0 }
    }

    pub fn one() -> Self {
        Field { v: 1 % Self::MOD }
    }

    /// fast exponentiation
    pub fn pow(self, mut exp: u128) -> Self {
        let mut base = self;
        let mut acc = Field::one();
        while exp > 0 {
            if exp & 1 != 0 {
                acc = acc * base;
            }
            base = base * base;
            exp >>= 1;
        }
        acc
    }

    /// Multiplicative inverse using Extended Euclidean algorithm (since modulus is prime)
    pub fn inv(self) -> Option<Self> {
        let (g, x, _y) = Self::egcd(self.v as i128, Self::MOD as i128);
        if g != 1 && g != -1 {
            return None;
        }
        let mut inv = x % (Self::MOD as i128);
        if inv < 0 {
            inv += Self::MOD as i128;
        }
        Some(Field { v: inv as u64 })
    }

    /// extended gcd for signed integers
    fn egcd(a: i128, b: i128) -> (i128, i128, i128) {
        if b == 0 {
            return (a.abs(), a.signum(), 0);
        }
        let (g, x1, y1) = Self::egcd(b, a % b);
        (g, y1, x1 - (a / b) * y1)
    }
}

impl Add for Field {
    type Output = Self;
    fn add(self, other: Self) -> Self {
        let s = (self.v as u128 + other.v as u128) % (Self::MOD as u128);
        Field::new(s)
    }
}

impl Sub for Field {
    type Output = Self;
    fn sub(self, other: Self) -> Self {
        let m = Self::MOD as u128;
        let a = self.v as u128;
        let b = other.v as u128;
        Field::new((a + m - (b % m)) % m)
    }
}

impl Mul for Field {
    type Output = Self;
    fn mul(self, other: Self) -> Self {
        Field::new((self.v as u128) * (other.v as u128))
    }
}