Struct DenseUnivariatePolynomial 

pub struct DenseUnivariatePolynomial<D>
where
    D: Domain,
{ /* private fields */ }

A dense univariate polynomial with coefficients in a domain D.

Example

use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let domain = IntegerDomain;
let p = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(2), Integer::from(1)],
);
let q = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(1)],
);
let r = p.mul(&q);
assert_eq!(r.coeffs(), &[
    Integer::from(1),
    Integer::from(3),
    Integer::from(3),
    Integer::from(1),
]);

Implementations

impl<D> DenseUnivariatePolynomial<D>

where D: Domain,

pub fn new(domain: D) -> DenseUnivariatePolynomial<D>

Create the zero polynomial over domain.

pub fn from_coeffs( domain: D, coeffs: Vec<<D as Domain>::Element>, ) -> DenseUnivariatePolynomial<D>

Create a polynomial from a vector of coefficients [a0, a1, ..., an].

Trailing zero coefficients are stripped automatically.

Example

use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let domain = IntegerDomain;
let p = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(0), Integer::from(2)],
);
assert_eq!(p.degree(), Some(2));
assert_eq!(p.coeff(2), Some(&Integer::from(2)));

pub fn domain(&self) -> &D

Return a reference to the coefficient domain.

pub fn coeffs(&self) -> &[<D as Domain>::Element]

Return the coefficients from constant term upward.

pub fn is_zero(&self) -> bool

Return whether this is the zero polynomial.

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

Return the degree of the polynomial, or None for the zero polynomial.

pub fn coeff(&self, n: usize) -> Option<&<D as Domain>::Element>

Return the coefficient of x^n, or None if the term is absent.

pub fn leading_coeff(&self) -> Option<&<D as Domain>::Element>

Return the leading coefficient, or None for the zero polynomial.

pub fn lcoeff(&self) -> <D as Domain>::Element

Convenience alias: return the leading coefficient, or the domain’s zero element for the zero polynomial.

pub fn constant(&self) -> <D as Domain>::Element

Return the constant term (coefficient of $x^0$), or the domain’s zero element for the zero polynomial.

pub fn zero(&self) -> DenseUnivariatePolynomial<D>

Return the zero polynomial with the same domain.

pub fn one(&self) -> DenseUnivariatePolynomial<D>

Return the constant polynomial 1 over the same domain.

pub fn is_one(&self) -> bool

Return whether this is the constant polynomial 1.

pub fn neg(&self) -> DenseUnivariatePolynomial<D>

Return the negation of this polynomial.

pub fn add( &self, other: &DenseUnivariatePolynomial<D>, ) -> DenseUnivariatePolynomial<D>

Add another polynomial.

pub fn sub( &self, other: &DenseUnivariatePolynomial<D>, ) -> DenseUnivariatePolynomial<D>

Subtract another polynomial.

pub fn mul_scalar( &self, scalar: &<D as Domain>::Element, ) -> DenseUnivariatePolynomial<D>

Multiply by a scalar coefficient.

pub fn mul( &self, other: &DenseUnivariatePolynomial<D>, ) -> DenseUnivariatePolynomial<D>

Multiply two polynomials.

Example

use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let domain = IntegerDomain;
let a = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(1)],
);
let b = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(-1)],
);
let c = a.mul(&b);
assert_eq!(c.coeffs(), &[Integer::from(1), Integer::from(0), Integer::from(-1)]);

pub fn mul_into( &self, other: &DenseUnivariatePolynomial<D>, buf: &mut Vec<<D as Domain>::Element>, )

Multiply two polynomials, reusing the provided buffer for the result.

The buffer is cleared and resized as needed. This avoids repeated heap allocation in hot loops (e.g. GCD, factorization).

After the call, buf contains the coefficients of the product (constant term first). If either polynomial is zero, buf is cleared.

pub fn eval(&self, x: &<D as Domain>::Element) -> <D as Domain>::Element

Evaluate the polynomial at x using Horner’s method.

The zero polynomial evaluates to the domain’s zero element.

Example

use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let domain = IntegerDomain;
let p = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(2), Integer::from(3)],
);
let value = p.eval(&Integer::from(2));
assert_eq!(value, Integer::from(17));

pub fn derivative(&self) -> DenseUnivariatePolynomial<D>

Return the formal derivative of this polynomial.

For p(x) = a_0 + a_1 x + a_2 x^2 + ... the derivative is p'(x) = a_1 + 2 a_2 x + 3 a_3 x^2 + ....

pub fn integral(&self) -> DenseUnivariatePolynomial<D>

Return the formal integral of this polynomial, with constant term zero.

For p(x) = a_0 + a_1 x + a_2 x^2 + ... the integral is ∫p(x) dx = 0 + a_0 x + (a_1/2) x^2 + (a_2/3) x^3 + ....

impl<D> DenseUnivariatePolynomial<D>

where D: EuclideanDomain,

pub fn mul_coeff( &self, c: &<D as Domain>::Element, ) -> DenseUnivariatePolynomial<D>

Multiply all coefficients by a constant.

Equivalent to mul_scalar but restricted to EuclideanDomain for consistency with div_coeff.

pub fn div_coeff( &self, c: &<D as Domain>::Element, ) -> DenseUnivariatePolynomial<D>

Divide all coefficients by a constant (must divide exactly).

Panics in debug mode if any coefficient is not divisible by c.

pub fn div_rem( &self, divisor: &DenseUnivariatePolynomial<D>, ) -> Option<(DenseUnivariatePolynomial<D>, DenseUnivariatePolynomial<D>)>

Divide this polynomial by another, returning (quotient, remainder).

Returns None if the divisor is the zero polynomial.

Example

use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let domain = IntegerDomain;
let p = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(0), Integer::from(-1)],
);
let q = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(1)],
);
let (quot, rem) = p.div_rem(&q).unwrap();
assert_eq!(quot.coeffs(), &[Integer::from(1), Integer::from(-1)]);
assert!(rem.is_zero());

pub fn pow(&self, n: u32) -> DenseUnivariatePolynomial<D>

Compute self^n by repeated squaring.

pub fn extended_gcd_poly( &self, other: &DenseUnivariatePolynomial<D>, ) -> (DenseUnivariatePolynomial<D>, DenseUnivariatePolynomial<D>, DenseUnivariatePolynomial<D>)

Compute the extended GCD of two polynomials: (g, s, t) such that s * self + t * other = g where g = gcd(self, other).

Uses the extended Euclidean algorithm.

pub fn diophantine( polys: &mut [DenseUnivariatePolynomial<D>], b: &DenseUnivariatePolynomial<D>, ) -> Vec<DenseUnivariatePolynomial<D>>

Polynomial CRT (diophantine solver).

Given a list of pairwise coprime polynomials polys and a target b, returns [s0, ..., sn] such that:

$$\sum_i s_i \cdot \prod_{j \neq i} p_j \equiv b \pmod{\prod_i p_i}$$

Uses the extended Euclidean algorithm recursively.

Panics

Panics if the polynomials are not pairwise coprime (i.e. the GCD is not a unit).

pub fn p_adic_expansion( &self, p: &DenseUnivariatePolynomial<D>, ) -> Vec<DenseUnivariatePolynomial<D>>

p-adic expansion of self with respect to p.

Returns [a0, a1, a2, ...] such that:

$$\text{self} = a_0 + a_1 \cdot p + a_2 \cdot p^2 + \cdots$$

where each $a_k$ has degree less than $\deg(p)$.

This is computed by repeated polynomial division (like integer p-adic expansion).

impl DenseUnivariatePolynomial<FiniteField>

NTT-accelerated multiplication for FiniteField polynomials.

When the ntt feature is enabled and the prime is NTT-friendly, large polynomial multiplications are performed using the Number Theoretic Transform in $O(n \log n)$ instead of Karatsuba’s $O(n^{1.585})$.

pub fn mul_ntt( &self, other: &DenseUnivariatePolynomial<FiniteField>, buf: &mut Vec<FiniteFieldElement>, )

Multiply two FiniteField polynomials, preferring NTT when possible.

Falls back to the generic Karatsuba/Schoolbook path when:

• The degree is below [NTT_THRESHOLD]
• The prime does not have a suitable root of unity
• The prime is too large for u64 representation

pub fn would_use_ntt( &self, other: &DenseUnivariatePolynomial<FiniteField>, ) -> bool

Returns true if NTT multiplication would be used for this pair.

impl<D> DenseUnivariatePolynomial<D>

where D: EuclideanDomain,

pub fn square_free_factorization( &self, ) -> Vec<(DenseUnivariatePolynomial<D>, usize)>

Compute the square-free factorization of this polynomial.

Returns a list of (factor, multiplicity) pairs. For example, (x+1)^2 * (x-1) yields [(x+1, 2), (x-1, 1)].

Example

use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let d = IntegerDomain;
// (x+1)^2*(x-1) = x^3 + x^2 - x - 1
let p = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(-1), Integer::from(-1), Integer::from(1), Integer::from(1),
]);
let factors = p.square_free_factorization();
assert_eq!(factors.len(), 2);

pub fn is_square_free(&self) -> bool

Check whether this polynomial is square-free.

A polynomial is square-free if gcd(p, p’) = 1.

impl DenseUnivariatePolynomial<IntegerDomain>

pub fn factor(&self) -> Vec<(DenseUnivariatePolynomial<IntegerDomain>, usize)>

Completely factor this primitive integer polynomial into monic irreducible factors with multiplicities.

The input must be primitive (coefficient content = 1). Use primitive_part to prepare an arbitrary integer polynomial before factoring.

Example

use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::DenseUnivariatePolynomial;

let d = IntegerDomain;
// x^2 - 1 = (x-1)(x+1)
let p = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(-1), Integer::from(0), Integer::from(1),
]);
let factors = p.factor();
assert_eq!(factors.len(), 2);

impl DenseUnivariatePolynomial<FiniteField>

pub fn factor(&self) -> Vec<(DenseUnivariatePolynomial<FiniteField>, usize)>

Completely factor this univariate polynomial over $\mathbb{F}_p$ into monic irreducible factors with multiplicities.

Example

use num_bigint::BigInt;
use ocas_domain::{Domain, FiniteField};
use ocas_poly::DenseUnivariatePolynomial;

let f = FiniteField::new(BigInt::from(5));
// x^2 - 1 over F_5
let p = DenseUnivariatePolynomial::from_coeffs(
    f.clone(), vec![f.element(4), f.element(0), f.element(1)]);
let factors = p.factor();
assert!(!factors.is_empty());

impl<D> DenseUnivariatePolynomial<D>

where D: EuclideanDomain,

pub fn gcd( &self, other: &DenseUnivariatePolynomial<D>, ) -> DenseUnivariatePolynomial<D>

Compute the greatest common divisor of self and other.

Uses the Euclidean algorithm with pseudo-remainders for non-field domains. The result is always primitive (content-free).

Example

use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let d = IntegerDomain;
let a = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(-1), Integer::from(0), Integer::from(1),
]); // x^2 - 1 = (x-1)(x+1)
let b = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(1), Integer::from(2), Integer::from(1),
]); // x^2 + 2x + 1 = (x+1)^2
let g = a.gcd(&b);
assert_eq!(g.coeffs(), &[Integer::from(1), Integer::from(1)]); // x + 1

pub fn content(&self) -> <D as Domain>::Element

Compute the content of this polynomial: the GCD of all its coefficients.

For the zero polynomial the content is zero.

pub fn primitive_part(&self) -> DenseUnivariatePolynomial<D>

Return the primitive part of this polynomial (polynomial / content).

impl<D> DenseUnivariatePolynomial<D>

where D: EuclideanDomain,

pub fn resultant( &self, other: &DenseUnivariatePolynomial<D>, ) -> <D as Domain>::Element

Compute the resultant of self and other using Brown’s PRS algorithm.

The resultant $\operatorname{Res}(a, b)$ is a scalar in the coefficient domain. It is zero if and only if $\gcd(a, b)$ is non-constant.

Example

use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let d = IntegerDomain;
// Res(x - 1, x - 2) = 1 - 2 = -1
let a = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(-1), Integer::from(1),
]);
let b = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(-2), Integer::from(1),
]);
assert_eq!(a.resultant(&b), Integer::from(-1));

impl<D> DenseUnivariatePolynomial<D>

where D: EuclideanDomain, <D as Domain>::Element: Display,

pub fn sturm_sequence(&self) -> Vec<DenseUnivariatePolynomial<D>>

Compute the Sturm sequence for this polynomial.

The Sturm sequence is: p0 = p, p1 = p’, p_{i+1} = -rem(p_{i-1}, p_i). The number of sign changes at x gives the number of real roots > x.

pub fn eval_f64(&self, x: f64) -> f64

Evaluate this polynomial at x as a floating-point value.

Uses Horner’s method with f64 arithmetic. For exact evaluation, use eval() with domain elements.

pub fn count_real_roots(&self) -> usize

Count the number of distinct real roots of this polynomial.

Uses Sturm’s theorem: count roots in (-∞, +∞).

pub fn isolate_real_roots(&self) -> Vec<RootInterval>

Isolate real roots: return a list of intervals, each containing exactly one real root.

Uses bisection with Sturm-based counting to find intervals.

pub fn refine_root(&self, interval: &RootInterval, tol: f64) -> RootInterval

Refine a root interval using bisection to the given tolerance.

Trait Implementations

impl<D> Clone for DenseUnivariatePolynomial<D>

where D: Clone + Domain, <D as Domain>::Element: Clone,

fn clone(&self) -> DenseUnivariatePolynomial<D>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<D> Debug for DenseUnivariatePolynomial<D>

where D: Debug + Domain, <D as Domain>::Element: Debug,

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

Formats the value using the given formatter.

impl<D> Eq for DenseUnivariatePolynomial<D>

where D: Eq + Domain, <D as Domain>::Element: Eq,

impl<D> PartialEq for DenseUnivariatePolynomial<D>

where D: PartialEq + Domain, <D as Domain>::Element: PartialEq,

fn eq(&self, other: &DenseUnivariatePolynomial<D>) -> bool

Equality operator ==.

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

Inequality operator !=.

impl<D> StructuralPartialEq for DenseUnivariatePolynomial<D>

where D: PartialEq + Domain, <D as Domain>::Element: PartialEq,