Module finite_field 

Finite Field Arithmetic for Modular GCD Algorithms

This module provides efficient arithmetic in finite fields Z_p (integers mod prime p) and polynomials over finite fields Z_p[x]. These are foundational for:

• Modular GCD algorithms (Zippel, Brown)
• Chinese Remainder Theorem reconstruction
• Sparse interpolation
• Industrial-strength polynomial computation
• Fast polynomial multiplication via NTT
• Polynomial factorization (Berlekamp, Hensel lifting)

Mathematical Background

A finite field Z_p contains integers {0, 1, 2, …, p-1} with arithmetic modulo prime p. Every non-zero element has a multiplicative inverse (Fermat’s little theorem: a^(p-1) = 1 mod p).

Key properties exploited:

• Division is always exact (multiplicative inverses exist)
• GCD algorithms terminate in polynomial time
• Evaluation at random points allows sparse reconstruction
• Number Theoretic Transform enables O(n log n) polynomial multiplication
• Factorization over Z_p enables factorization over Z via Hensel lifting

Module Organization

• element: Zp type (field elements)
• poly: PolyZp type (polynomials over Z_p)
• gcd: GCD algorithms for PolyZp
• ntt: Fast polynomial multiplication via Number Theoretic Transform
• berlekamp: Polynomial factorization (Berlekamp’s algorithm, Hensel lifting)
• bridge: Conversion to/from Expression

Performance Considerations

Following the Rust Performance Book guidelines:

• Use u64 for field elements to leverage native CPU operations
• Avoid branches in hot paths using conditional moves
• Preallocate vectors with known capacity
• Use #[inline] for small, frequently-called functions
• Use NTT for large polynomial multiplication (O(n log n) vs O(n²))

References

• [Zippel79] Zippel, R. “Probabilistic algorithms for sparse polynomials”
• [GCL92] Geddes, Czapor, Labahn. “Algorithms for Computer Algebra”
• [CT65] Cooley, Tukey. “An algorithm for the machine calculation of complex Fourier series”

Modules

berlekamp

Polynomial Factorization over Finite Fields

educational

Educational explanations for finite field operations

Structs

PolyZp

Polynomial over finite field Z_p[x]

Zp

Element of finite field Z_p (integers modulo prime p)

Enums

FiniteFieldError

Error types for finite field operations

Constants

NTT_PRIME_1

Common NTT-friendly prime: 2013265921 = 15 * 2^27 + 1 Supports NTT up to degree 2^27 - 1

NTT_PRIME_2

Common NTT-friendly prime: 469762049 = 7 * 2^26 + 1 Supports NTT up to degree 2^26 - 1

NTT_PRIME_3

Common NTT-friendly prime: 1004535809 = 479 * 2^21 + 1 Supports NTT up to degree 2^21 - 1

NTT_THRESHOLD

Threshold for switching from naive to NTT multiplication Empirically determined crossover point where NTT becomes faster Lowered to 32 for better performance on medium-sized polynomials

Functions

content

Compute content (GCD of all coefficients)

extended_gcd

Extended Euclidean algorithm

is_prime

Check if a number is prime using trial division

multiply_auto

Multiply two polynomials using automatic threshold-based selection

ntt_multiply

Fast polynomial multiplication using optimized NTT

Type Aliases

FiniteFieldResult

Result type for finite field operations