/// Simple finite field arithmetic modulo a prime p (u64).
/// Uses u128 intermediates to avoid overflow on multiplication.
use core::fmt;
#[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 } }
pub fn add(self, other: Self) -> Self {
let mut s = self.v as u128 + other.v as u128;
s %= Self::MOD as u128;
Field::new(s)
}
pub 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)
}
pub fn mul(self, other: Self) -> Self {
let r = (self.v as u128) * (other.v as u128);
Field::new(r)
}
/// 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.mul(base); }
base = base.mul(base);
exp >>= 1;
}
acc
}
/// Multiplicative inverse using Extended Euclidean on integers (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)
}
}