Struct PolyZp 

pub struct PolyZp { /* private fields */ }

Polynomial over finite field Z_p[x]

Represented as a vector of coefficients where index i is the coefficient of x^i. The zero polynomial has empty coefficients.

Invariants

• Leading coefficient is always non-zero (except for zero polynomial)
• Coefficients are normalized (0 <= c < p)

Memory Layout

Uses Vec<u64> for coefficients plus a u64 for the modulus. This is cache-friendly and allows efficient iteration.

Examples

use mathhook_core::algebra::PolyZp;

// Create polynomial x^2 + 2x + 3 mod 7
let p = PolyZp::from_coeffs(vec![3, 2, 1], 7);
assert_eq!(p.degree(), Some(2));

// Evaluate at x = 2: 4 + 4 + 3 = 11 ≡ 4 (mod 7)
let result = p.evaluate(2);
assert_eq!(result.value(), 4);

Implementations

impl PolyZp

pub fn from_expression(expr: &Expression, var: &Symbol, prime: u64) -> Self

Convert a univariate Expression polynomial to PolyZp

Extracts integer coefficients from an Expression and reduces them modulo the prime. Supports polynomials with integer coefficients in a single variable.

Arguments

• expr - The Expression to convert (must be polynomial in var)
• var - The variable of the polynomial
• prime - The prime modulus

Returns

A PolyZp with coefficients reduced mod prime.

Examples

use mathhook_core::algebra::PolyZp;
use mathhook_core::{expr, symbol};

let x = symbol!(x);
let poly = expr!((x^2) + (2*x) + 3);  // x^2 + 2x + 3
let poly_zp = PolyZp::from_expression(&poly, &x, 7);
assert_eq!(poly_zp.coefficients(), &[3, 2, 1]);

pub fn to_expression(&self, var: &Symbol) -> Expression

Convert PolyZp back to an Expression

Creates a polynomial Expression from the finite field polynomial. Uses symmetric representation for coefficients (values > p/2 become negative).

Arguments

• var - The variable to use in the Expression

Returns

An Expression representing the polynomial.

Examples

use mathhook_core::algebra::PolyZp;
use mathhook_core::symbol;

let poly = PolyZp::from_coeffs(vec![3, 2, 1], 7);  // x^2 + 2x + 3
let x = symbol!(x);
let expr = poly.to_expression(&x);
// expr represents x^2 + 2*x + 3

pub fn to_expression_unsigned(&self, var: &Symbol) -> Expression

Convert PolyZp to Expression using standard (non-symmetric) representation

Similar to to_expression, but coefficients stay in [0, p-1] range.

Arguments

• var - The variable to use in the Expression

impl PolyZp

pub fn gcd(&self, other: &Self) -> FiniteFieldResult<Self>

Compute GCD using Euclidean algorithm

Returns a monic GCD (leading coefficient = 1).

Examples

use mathhook_core::algebra::PolyZp;

// gcd(x^2 - 1, x - 1) = x - 1
let p1 = PolyZp::from_signed_coeffs(&[-1, 0, 1], 7);  // x^2 - 1
let p2 = PolyZp::from_signed_coeffs(&[-1, 1], 7);      // x - 1
let gcd = p1.gcd(&p2).unwrap();
// Should be x - 1 (monic), which is [6, 1] in Z_7
assert_eq!(gcd.degree(), Some(1));

pub fn extended_gcd( &self, other: &Self, ) -> FiniteFieldResult<(Self, Self, Self)>

Extended Euclidean algorithm for polynomials

Returns (gcd, s, t) such that gcd = sself + tother.

Examples

use mathhook_core::algebra::PolyZp;

let p1 = PolyZp::from_coeffs(vec![1, 2, 1], 7);
let p2 = PolyZp::from_coeffs(vec![1, 1], 7);
let (gcd, s, t) = p1.extended_gcd(&p2).unwrap();

// Verify: gcd = s*p1 + t*p2
let check = s.mul(&p1).add(&t.mul(&p2));
assert_eq!(gcd.coefficients(), check.coefficients());

pub fn mod_inverse(&self, modpoly: &Self) -> FiniteFieldResult<Self>

Compute modular inverse of a polynomial mod another polynomial

Returns polynomial p such that self * p ≡ 1 (mod modpoly)

Arguments

• modpoly - The modulus polynomial

Returns

The inverse if it exists (gcd = 1), error otherwise.

impl PolyZp

pub fn evaluate(&self, x: u64) -> Zp

Evaluate polynomial at a point using Horner’s method

This is O(n) multiplications for degree n polynomial.

Arguments

• x - The evaluation point

Examples

use mathhook_core::algebra::PolyZp;

// p(x) = x^2 + 2x + 3
let p = PolyZp::from_coeffs(vec![3, 2, 1], 7);
// p(2) = 4 + 4 + 3 = 11 ≡ 4 (mod 7)
assert_eq!(p.evaluate(2).value(), 4);

pub fn evaluate_zp(&self, x: Zp) -> Zp

Evaluate polynomial at a field element

pub fn make_monic(&self) -> FiniteFieldResult<Self>

Make the polynomial monic (leading coefficient = 1)

Divides all coefficients by the leading coefficient.

Returns

Ok(monic_poly) if non-zero, Err if zero polynomial.

pub fn shift(&self, n: usize) -> Self

Shift polynomial by multiplying by x^n

impl PolyZp

pub fn add(&self, other: &Self) -> Self

Add two polynomials

pub fn sub(&self, other: &Self) -> Self

Subtract two polynomials

pub fn mul(&self, other: &Self) -> Self

Multiply two polynomials using naive algorithm

Uses naive O(n*m) convolution multiplication. This is the baseline algorithm that works for any modulus and is efficient for small polynomials.

For large polynomials with NTT-friendly primes, consider using mul_fast() which automatically switches to O(n log n) NTT multiplication.

Complexity

• Time: O(n*m) where n = deg(self), m = deg(other)
• Space: O(n + m) for result coefficients

Performance

• Efficient for: Small polynomials (degree < 64)
• Alternative for large: Use mul_fast() for automatic NTT optimization

Examples

use mathhook_core::algebra::PolyZp;

let a = PolyZp::from_coeffs(vec![1, 1], 7);  // x + 1
let b = PolyZp::from_coeffs(vec![1, 1], 7);  // x + 1
let product = a.mul(&b);                      // x^2 + 2x + 1
assert_eq!(product.coefficients(), &[1, 2, 1]);

pub fn mul_fast(&self, other: &Self) -> Self

Fast polynomial multiplication with automatic algorithm selection

Automatically chooses between naive O(n²) and NTT O(n log n) multiplication based on polynomial degree and prime modulus support.

Algorithm Selection

• Small polynomials (degree ≤ 64): Uses naive multiplication
• Large polynomials (degree > 64) with NTT-friendly prime: Uses NTT
• Unsupported prime: Falls back to naive multiplication

NTT-Friendly Primes

• 2013265921 = 15 * 2^27 + 1 (supports degree up to 2^27 - 1)
• 469762049 = 7 * 2^26 + 1 (supports degree up to 2^26 - 1)
• 1004535809 = 479 * 2^21 + 1 (supports degree up to 2^21 - 1)

Performance

For degree 1000 polynomials: ~10x faster than naive For degree 10000 polynomials: ~100x faster than naive

Examples

use mathhook_core::algebra::PolyZp;

// Small polynomials: automatically uses naive
let a = PolyZp::from_coeffs(vec![1, 2, 3], 7);
let b = PolyZp::from_coeffs(vec![4, 5], 7);
let product = a.mul_fast(&b);

// Large polynomials with NTT prime: automatically uses NTT
let p = 2013265921;  // NTT-friendly prime
let large_a = PolyZp::from_coeffs(vec![1; 100], p);
let large_b = PolyZp::from_coeffs(vec![2; 100], p);
let fast_product = large_a.mul_fast(&large_b);  // Uses NTT

pub fn scale(&self, c: Zp) -> Self

Multiply polynomial by a scalar

pub fn div_rem(&self, divisor: &Self) -> FiniteFieldResult<(Self, Self)>

Polynomial division with remainder

Returns (quotient, remainder) such that self = quotient * divisor + remainder and degree(remainder) < degree(divisor).

Arguments

• divisor - The divisor polynomial (must be non-zero)

Returns

Ok((quotient, remainder)) or error if divisor is zero.

Examples

use mathhook_core::algebra::PolyZp;

// (x^2 + 2x + 1) / (x + 1) = (x + 1, 0)
let dividend = PolyZp::from_coeffs(vec![1, 2, 1], 7);
let divisor = PolyZp::from_coeffs(vec![1, 1], 7);
let (q, r) = dividend.div_rem(&divisor).unwrap();
assert_eq!(q.coefficients(), &[1, 1]);
assert!(r.is_zero());

impl PolyZp

pub fn from_coeffs(coeffs: Vec<u64>, modulus: u64) -> Self

Create polynomial from owned coefficients

Use this when you already have an owned Vec<u64> to avoid extra allocation. This is more efficient than from_coeffs which always copies.

Arguments

• coeffs - Owned vector of coefficients where index i is coefficient of x^i
• modulus - The prime modulus

Examples

use mathhook_core::algebra::PolyZp;

// x^2 + 2x + 3 mod 7 - takes ownership, no extra allocation
let coeffs = vec![3, 2, 1];
let p = PolyZp::from_coeffs(coeffs, 7);
assert_eq!(p.degree(), Some(2));

pub fn from_signed_coeffs(coeffs: &[i64], modulus: u64) -> Self

Create polynomial from signed coefficients

pub fn zero(modulus: u64) -> Self

Create the zero polynomial

pub fn constant(c: u64, modulus: u64) -> Self

Create the constant polynomial c

pub fn x(modulus: u64) -> Self

Create the polynomial x

pub fn x_minus_a(a: u64, modulus: u64) -> Self

Create the monic polynomial x - a

pub fn is_zero(&self) -> bool

Check if this is the zero polynomial

pub fn is_constant(&self) -> bool

Check if this is a constant polynomial

pub fn degree(&self) -> Option<usize>

Get the degree of the polynomial

Returns None for the zero polynomial, Some(d) otherwise.

pub fn leading_coeff(&self) -> Option<Zp>

Get the leading coefficient

Returns None for the zero polynomial.

pub fn coeff(&self, i: usize) -> Zp

Get coefficient of x^i

pub fn modulus(&self) -> u64

Get the modulus

pub fn coefficients(&self) -> &[u64]

Get coefficients as slice

Trait Implementations

impl Clone for PolyZp

fn clone(&self) -> PolyZp

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for PolyZp

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Display for PolyZp

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq for PolyZp

fn eq(&self, other: &PolyZp) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for PolyZp

impl StructuralPartialEq for PolyZp