field-cat 0.1.0

//! The [`F101`] toy field: integers modulo `101`.
//!
//! A small prime field useful for tests and small inspectable
//! examples.  Every nonzero element has a multiplicative inverse.

use crate::bytes::FieldBytes;
use crate::error::Error;
use crate::field::Field;

/// The [`F101`] modulus: `101`.
const P: u64 = 101;

/// A field element modulo `101`.
///
/// # Examples
///
/// ```
/// use field_cat::{F101, Field};
///
/// let a = F101::new(50);
/// let b = F101::new(30);
/// assert_eq!((a + b).value(), 80);
///
/// // Values larger than 101 are reduced.
/// assert_eq!(F101::new(103), F101::new(2));
///
/// // Multiplicative inverse via Fermat's little theorem.
/// let inv = F101::new(7).inv()?;
/// assert_eq!(F101::new(7) * inv, F101::one());
/// # Ok::<(), field_cat::Error>(())
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct F101(u64);

impl F101 {
    /// Create a new field element, reducing modulo `101`.
    #[must_use]
    pub fn new(value: u64) -> Self {
        Self(value % P)
    }

    /// The underlying integer value in `[0, 101)`.
    #[must_use]
    pub fn value(self) -> u64 {
        self.0
    }
}

impl core::fmt::Display for F101 {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl std::ops::Add for F101 {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        Self((self.0 + rhs.0) % P)
    }
}

impl std::ops::Sub for F101 {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        Self((self.0 + P - rhs.0) % P)
    }
}

impl std::ops::Mul for F101 {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self {
        Self((self.0 * rhs.0) % P)
    }
}

impl std::ops::Neg for F101 {
    type Output = Self;
    fn neg(self) -> Self {
        Self((P - self.0) % P)
    }
}

impl Field for F101 {
    fn zero() -> Self {
        Self(0)
    }

    fn one() -> Self {
        Self(1)
    }

    fn inv(&self) -> Result<Self, Error> {
        if self.0 == 0 {
            Err(Error::DivisionByZero)
        } else {
            // Fermat's little theorem: a^(p-2) is the inverse for prime p.
            Ok(Self(pow_mod(self.0, P - 2, P)))
        }
    }
}

impl FieldBytes for F101 {
    fn to_le_bytes(&self) -> Vec<u8> {
        // Values fit in a single byte.
        u8::try_from(self.0).map(|b| vec![b]).unwrap_or_default()
    }

    fn from_le_bytes(bytes: &[u8]) -> Result<Self, Error> {
        bytes
            .first()
            .map(|&b| Self::new(u64::from(b)))
            .ok_or(Error::InvalidFieldEncoding)
    }
}

/// Modular exponentiation `base^exp mod modulus`.
///
/// Builds the powers `base^(2^i)` lazily via `successors`, then
/// folds the ones whose bit in `exp` is set.  Linear in the bit
/// width of `exp`.
fn pow_mod(base: u64, exp: u64, modulus: u64) -> u64 {
    std::iter::successors(Some(base % modulus), |&b| Some((b * b) % modulus))
        .zip(0..u64::BITS)
        .filter(|&(_, i)| (exp >> i) & 1 == 1)
        .map(|(p, _)| p)
        .fold(1u64, |acc, p| (acc * p) % modulus)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn zero_is_additive_identity() {
        let a = F101::new(42);
        assert_eq!(a + F101::zero(), a);
        assert_eq!(F101::zero() + a, a);
    }

    #[test]
    fn one_is_multiplicative_identity() {
        let a = F101::new(42);
        assert_eq!(a * F101::one(), a);
        assert_eq!(F101::one() * a, a);
    }

    #[test]
    fn additive_inverse() {
        let a = F101::new(42);
        assert_eq!(a + (-a), F101::zero());
    }

    #[test]
    fn multiplicative_inverse() -> Result<(), Error> {
        let a = F101::new(42);
        let a_inv = a.inv()?;
        assert_eq!(a * a_inv, F101::one());
        Ok(())
    }

    #[test]
    fn inverse_of_zero_fails() {
        let result = F101::zero().inv();
        assert!(result.is_err());
    }

    #[test]
    fn all_nonzero_elements_have_inverses() -> Result<(), Error> {
        (1u64..101).try_for_each(|i| {
            let a = F101::new(i);
            let a_inv = a.inv()?;
            assert_eq!(a * a_inv, F101::one(), "failed for {i}");
            Ok(())
        })
    }

    #[test]
    fn subtraction_is_add_neg() {
        let a = F101::new(50);
        let b = F101::new(30);
        assert_eq!(a - b, a + (-b));
    }

    #[test]
    fn multiplication_is_commutative() {
        let a = F101::new(7);
        let b = F101::new(13);
        assert_eq!(a * b, b * a);
    }

    #[test]
    fn distributivity() {
        let a = F101::new(3);
        let b = F101::new(5);
        let c = F101::new(7);
        assert_eq!(a * (b + c), a * b + a * c);
    }

    #[test]
    fn new_reduces_mod_101() {
        assert_eq!(F101::new(202), F101::new(0));
        assert_eq!(F101::new(103), F101::new(2));
    }

    #[test]
    fn bytes_roundtrip() -> Result<(), Error> {
        let a = F101::new(42);
        let bytes = a.to_le_bytes();
        let b = F101::from_le_bytes(&bytes)?;
        assert_eq!(a, b);
        Ok(())
    }

    #[test]
    fn bytes_empty_fails() {
        let result = F101::from_le_bytes(&[]);
        assert!(result.is_err());
    }
}