mathhook_core/core/polynomial/
finite_field.rs

1//! Finite Field Arithmetic for Modular GCD Algorithms
2//!
3//! This module provides efficient arithmetic in finite fields Z_p (integers mod prime p)
4//! and polynomials over finite fields `Z_p[x]`. These are foundational for:
5//!
6//! - **Modular GCD algorithms** (Zippel, Brown)
7//! - **Chinese Remainder Theorem reconstruction**
8//! - **Sparse interpolation**
9//! - **Industrial-strength polynomial computation**
10//! - **Fast polynomial multiplication via NTT**
11//! - **Polynomial factorization** (Berlekamp, Hensel lifting)
12//!
13//! # Mathematical Background
14//!
15//! A finite field Z_p contains integers {0, 1, 2, ..., p-1} with arithmetic modulo prime p.
16//! Every non-zero element has a multiplicative inverse (Fermat's little theorem: a^(p-1) = 1 mod p).
17//!
18//! Key properties exploited:
19//! - Division is always exact (multiplicative inverses exist)
20//! - GCD algorithms terminate in polynomial time
21//! - Evaluation at random points allows sparse reconstruction
22//! - Number Theoretic Transform enables O(n log n) polynomial multiplication
23//! - Factorization over Z_p enables factorization over Z via Hensel lifting
24//!
25//! # Module Organization
26//!
27//! - `element`: `Zp` type (field elements)
28//! - `poly`: `PolyZp` type (polynomials over Z_p)
29//! - `gcd`: GCD algorithms for PolyZp
30//! - `ntt`: Fast polynomial multiplication via Number Theoretic Transform
31//! - `berlekamp`: Polynomial factorization (Berlekamp's algorithm, Hensel lifting)
32//! - `bridge`: Conversion to/from Expression
33//!
34//! # Performance Considerations
35//!
36//! Following the Rust Performance Book guidelines:
37//! - Use `u64` for field elements to leverage native CPU operations
38//! - Avoid branches in hot paths using conditional moves
39//! - Preallocate vectors with known capacity
40//! - Use `#[inline]` for small, frequently-called functions
41//! - Use NTT for large polynomial multiplication (O(n log n) vs O(n²))
42//!
43//! # References
44//!
45//! - `[Zippel79]` Zippel, R. "Probabilistic algorithms for sparse polynomials"
46//! - `[GCL92]` Geddes, Czapor, Labahn. "Algorithms for Computer Algebra"
47//! - `[CT65]` Cooley, Tukey. "An algorithm for the machine calculation of complex Fourier series"
48
49pub mod berlekamp;
50mod bridge;
51mod element;
52mod gcd;
53mod ntt;
54mod poly;
55
56use std::fmt;
57
58/// Error types for finite field operations
59#[derive(Debug, Clone, PartialEq)]
60pub enum FiniteFieldError {
61    /// Modulus must be a prime number
62    NonPrimeModulus { modulus: u64 },
63
64    /// Division by zero in finite field
65    DivisionByZero,
66
67    /// Modular inverse does not exist (gcd(a, p) != 1)
68    NoInverse { element: u64, modulus: u64 },
69
70    /// Polynomial is empty (no coefficients)
71    EmptyPolynomial,
72
73    /// Degree mismatch in polynomial operation
74    DegreeMismatch {
75        expected: usize,
76        got: usize,
77        operation: &'static str,
78    },
79
80    /// Overflow during computation
81    Overflow { operation: &'static str },
82
83    /// Invalid evaluation point
84    InvalidEvaluationPoint { reason: String },
85}
86
87impl fmt::Display for FiniteFieldError {
88    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
89        match self {
90            FiniteFieldError::NonPrimeModulus { modulus } => {
91                write!(f, "modulus {} is not prime", modulus)
92            }
93            FiniteFieldError::DivisionByZero => {
94                write!(f, "division by zero in finite field")
95            }
96            FiniteFieldError::NoInverse { element, modulus } => {
97                write!(
98                    f,
99                    "no multiplicative inverse for {} mod {} (gcd != 1)",
100                    element, modulus
101                )
102            }
103            FiniteFieldError::EmptyPolynomial => {
104                write!(f, "polynomial has no coefficients")
105            }
106            FiniteFieldError::DegreeMismatch {
107                expected,
108                got,
109                operation,
110            } => {
111                write!(f, "{} expected degree {}, got {}", operation, expected, got)
112            }
113            FiniteFieldError::Overflow { operation } => {
114                write!(f, "overflow during {}", operation)
115            }
116            FiniteFieldError::InvalidEvaluationPoint { reason } => {
117                write!(f, "invalid evaluation point: {}", reason)
118            }
119        }
120    }
121}
122
123impl std::error::Error for FiniteFieldError {}
124
125/// Result type for finite field operations
126pub type FiniteFieldResult<T> = Result<T, FiniteFieldError>;
127
128// Re-export from submodules
129pub use bridge::educational;
130pub use element::{extended_gcd, is_prime, Zp};
131pub use gcd::content;
132pub use ntt::{multiply_auto, ntt_multiply, NTT_PRIME_1, NTT_PRIME_2, NTT_PRIME_3, NTT_THRESHOLD};
133pub use poly::PolyZp;
mathhook_core/core/polynomial/finite_field.rs

mathhook_core/core/polynomial/
finite_field.rs
