Foundations: Polynomial Algebra

Polynomial algebra is the cornerstone of symbolic computation. This chapter starts from the basic definitions of polynomial rings, progressively introduces monomial orders, the multivariate division algorithm, and Hilbert's basis theorem, and explains how oCAS implements these concepts in Rust.

Prerequisites

Before reading this chapter, the following background is recommended:

• Abstract algebra: basic notions of groups, rings, and fields (identity element, zero divisors, integral domains)
• Linear algebra: vector spaces, linear independence, bases
• Mathematical induction: used to prove termination of division algorithms

For review, see the learning-path recommendations in the Mathematics Overview.

Basic Concepts

Univariate Polynomial Rings

Let $\mathbb{F}$ be a field (such as $\mathbb{Q}$ or $\mathbb{F}_p$). The univariate polynomial ring $\mathbb{F}[x]$ is the set of all expressions of the form

$$f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$$

where $a_i \in \mathbb{F}$ and $n \geq 0$.

Definition (degree). For a nonzero polynomial $f = \sum_{i=0}^n a_i x^i$ ($a_n \neq 0$), its degree is

$$\deg(f) = n$$

The degree of the zero polynomial $f = 0$ is conventionally $-\infty$ (represented as None in implementations).

Definition (leading coefficient). The leading coefficient of $f$ is $\text{lc}(f) = a_n$. When $\text{lc}(f) = 1$, $f$ is called monic.

Properties:

Multivariate Polynomial Rings

Let $\mathbb{F}$ be a field and $x_1, x_2, \ldots, x_n$ be $n$ indeterminates. The multivariate polynomial ring $\mathbb{F}[x_1, \ldots, x_n]$ is the set of all finite sums

$$f = \sum_{\alpha \in \mathbb{N}^n} c_\alpha , \mathbf{x}^\alpha$$

where $\alpha = (\alpha_1, \ldots, \alpha_n) \in \mathbb{N}^n$ is called an exponent vector, $\mathbf{x}^\alpha = x_1^{\alpha_1} x_2^{\alpha_2} \cdots x_n^{\alpha_n}$ is called a monomial, and $c_\alpha \in \mathbb{F}$ is called a coefficient.

Definition (total degree). The total degree of a monomial $\mathbf{x}^\alpha$ is $|\alpha| = \alpha_1 + \cdots + \alpha_n$. The total degree of a polynomial $f$ is $\deg(f) = \max{|\alpha| : c_\alpha \neq 0}$.

Definition (partial degree). The partial degree of a polynomial $f$ with respect to the variable $x_i$ is $\deg_{x_i}(f) = \max{\alpha_i : c_\alpha \neq 0}$.

Important distinction: The univariate polynomial ring $\mathbb{F}[x]$ is a principal ideal domain (PID) — every ideal is generated by a single polynomial. The multivariate polynomial ring $\mathbb{F}[x_1, \ldots, x_n]$ ($n \geq 2$) is no longer a PID; this is the starting point of Gröbner basis theory — see Gröbner Basis Theory.

Internal Representations of Polynomials

There are two basic computer representations of polynomials:

In oCAS, DenseUnivariatePolynomial uses the dense representation, while SparseMultivariatePolynomial uses the sparse representation. See § Implementation in oCAS.

Monomial Orders

In a multivariate polynomial ring, "who is the leading term" is no longer obvious — we need a rule for comparing monomials.

Definition (monomial order). A monomial order on $\mathbb{N}^n$ is a total order $\succ$ satisfying:

1. Well-ordering: every nonempty subset of $\mathbb{N}^n$ has a least element (equivalently: $0 \preceq \alpha$ for all $\alpha$)
2. Compatibility: if $\alpha \succ \beta$, then $\alpha + \gamma \succ \beta + \gamma$ for all $\gamma \in \mathbb{N}^n$

These two conditions guarantee termination of polynomial division. The three most commonly used monomial orders are introduced below.

Lexicographic Order (Lex)

$x^\alpha \succ_{\text{lex}} x^\beta$ if and only if the leftmost nonzero component of $\alpha - \beta$ is positive.

Equivalent description: compare the exponent vectors component by component from left to right; the first position where they differ decides the order.

Example: In $\mathbb{F}[x, y, z]$, ordered lexicographically:

$$x^2 y^3 z \succ_{\text{lex}} x^2 y^2 z^3 \succ_{\text{lex}} x y^5 \succ_{\text{lex}} y^{100} \succ_{\text{lex}} z^{100}$$

The characteristic of the lexicographic order is "elimination": if $x_1 \succ x_2 \succ \cdots \succ x_n$, then the leading term under the lexicographic order has maximal degree in $x_1$. This makes lexicographic bases naturally elimination-oriented.

Graded Lexicographic Order (Grlex)

$x^\alpha \succ_{\text{grlex}} x^\beta$ if and only if:

1. $|\alpha| > |\beta|$, or
2. $|\alpha| = |\beta|$ and $\alpha \succ_{\text{lex}} \beta$

That is, sort by total degree first; within the same total degree, sort lexicographically.

Example: In $\mathbb{F}[x, y]$, $\deg(x^2) = 2$, $\deg(xy) = 2$, $\deg(y^3) = 3$, hence

$$y^3 \succ_{\text{grlex}} x^2 \succ_{\text{grlex}} xy$$

Graded Reverse Lexicographic Order (Grevlex)

$x^\alpha \succ_{\text{grevlex}} x^\beta$ if and only if:

1. $|\alpha| > |\beta|$, or
2. $|\alpha| = |\beta|$ and the rightmost nonzero component of $\alpha - \beta$ is negative

That is, sort by total degree first; within the same total degree, compare from right to left, and the smaller one is greater.

Example: In $\mathbb{F}[x, y, z]$, $x^2 y$ and $x y^2$ both have total degree 3. $\alpha - \beta = (1, -1, 0)$; the rightmost nonzero component is $-1$ (negative), hence

$$x^2 y \succ_{\text{grevlex}} x y^2$$

The key advantage of Grevlex is computational: among monomials of the same total degree, Grevlex tends to keep the exponents of low-indexed variables smaller, which produces smaller intermediate polynomials in Gröbner basis computations.

Comparing the Three Orders

Note: In the table above, rank 1 means "largest" under the corresponding order. Both Grlex and Grevlex sort by total degree first, so $y^3$ (total degree 3) comes before $x^2$ and $xy$ (total degree 2). In two variables, Grlex and Grevlex coincide: for $x^2$ and $xy$, the rightmost nonzero component of $(2,0) - (1,1) = (1, -1)$ is $-1 < 0$, so both orders give $x^2 \succ xy$. The two orders differ only from $n \geq 3$ variables onward; for example, compare $xz^2$ and $y^3$ (total degree 3 each): under Grlex, $xz^2 \succ y^3$ (lexicographic tie-break: $(1,0,2) > (0,3,0)$), while under Grevlex, $(0,3,0) - (1,0,2) = (-1,3,-2)$ has rightmost nonzero component $-2 < 0$, so $y^3 \succ_{\text{grevlex}} xz^2$.

Re-verify the Grevlex tie-break: $x^2 y$ vs $x y^2$: $(2,1) - (1,2) = (1, -1)$; the rightmost nonzero component is $-1 < 0$, so $x^2 y \succ_{\text{grevlex}} xy^2$.

Extended Orders

Besides the three basic orders above, oCAS also supports the following parameterized orders:

Weight order (WeightOrder): assigns a weight $w_i$ to each variable and orders by the decreasing value of $\sum w_i \alpha_i$. When the weight vector is $(1, 1, \ldots, 1)$, this degenerates to the total-degree order.

Matrix order (MatrixOrder): given an $n \times n$ integer matrix $M$, $\alpha \succ \beta$ if and only if $M\alpha >_{\text{lex}} M\beta$. The matrix order is the complete generalization of all linear monomial orders. In particular, an elimination order can be constructed via MatrixOrder::elimination_order(elim_vars, n_vars), which is used to eliminate variables from polynomial systems.

Block order (BlockOrder): partitions the variables into contiguous blocks, each block using an independent sub-order (Lex, Grlex, or Grevlex). The standard form of an elimination order is "the first $k$ variables use Lex, the rest use Grevlex".

Core Theory

Univariate Division with Remainder

Theorem (division with remainder). Let $\mathbb{F}$ be a field and $f, g \in \mathbb{F}[x]$ with $g \neq 0$. There exist unique $q, r \in \mathbb{F}[x]$ such that

$$f = q \cdot g + r, \quad \deg(r) < \deg(g)$$

Algorithm (successive elimination of leading terms):

Input: f, g (g ≠ 0)
Output: quotient q, remainder r

q ← 0, r ← f
while r ≠ 0 and deg(r) ≥ deg(g):
    t ← lc(r) / lc(g) · x^(deg(r) - deg(g))
    q ← q + t
    r ← r - t · g
return (q, r)

Termination: at each step $\deg(r)$ strictly decreases (or $r$ becomes zero), so the algorithm always terminates.

Generalization to integral domains: When the coefficient ring is a Euclidean domain (such as $\mathbb{Z}$), division with remainder still exists, but pseudo-division is needed to avoid fractions. In oCAS, DenseUnivariatePolynomial::div_rem implements this by performing division with remainder on the leading coefficients via EuclideanDomain::div_rem.

Multivariate Division with Remainder

The multivariate case is far more complicated than the univariate one — the quotient and remainder are not unique; they depend on the monomial order and the order of division.

Theorem (multivariate division algorithm). Let $\mathbb{F}$ be a field and $f, g_1, \ldots, g_s \in \mathbb{F}[x_1, \ldots, x_n]$ with $g_i \neq 0$. Fix a monomial order. There is an algorithm that computes $q_1, \ldots, q_s, r \in \mathbb{F}[x_1, \ldots, x_n]$ such that

$$f = q_1 g_1 + q_2 g_2 + \cdots + q_s g_s + r$$

where no nonzero term of $r$ is divisible by any $\text{lt}(g_i)$. Such an $r$ is called the remainder (or normal form) of $f$ with respect to ${g_1, \ldots, g_s}$.

Algorithm:

Input: f, G = [g1, ..., gs]
Output: q1, ..., qs, r

r ← 0, p ← f
while p ≠ 0:
    if ∃ i such that lt(gi) | lt(p):
        choose the smallest such i
        qi ← qi + lt(p) / lt(gi)
        p ← p - (lt(p) / lt(gi)) · gi
    else:
        r ← r + lt(p)
        p ← p - lt(p)
return (q1, ..., qs, r)

Key properties:

1. Termination: guaranteed by the well-ordering of the monomial order
2. Non-uniqueness: the remainder $r$ depends on the order of division $g_1, \ldots, g_s$. Different orders may produce different remainders
3. The key role of Gröbner bases: when ${g_1, \ldots, g_s}$ forms a Gröbner basis, the remainder $r$ is unique — this is one of the core values of Gröbner bases

Example: Take $f = x^2 y + x y^2 + y^2$, $g_1 = xy - 1$, $g_2 = y^2 - 1$, using the Grevlex order.

Step 1: $\text{lt}(f) = x^2 y$, and $\text{lt}(g_1) = xy$ divides $x^2 y$.

$$f \leftarrow f - x \cdot g_1 = x^2 y + x y^2 + y^2 - x(xy - 1) = x y^2 + y^2 + x$$

Step 2: $\text{lt}(p) = x y^2$, and $\text{lt}(g_1) = xy$ divides $x y^2$.

$$p \leftarrow x y^2 + y^2 + x - y \cdot g_1 = x y^2 + y^2 + x - y(xy - 1) = y^2 + x + y$$

Step 3: $\text{lt}(p) = y^2$, and $\text{lt}(g_2) = y^2$ divides $y^2$.

$$p \leftarrow y^2 + x + y - 1 \cdot g_2 = y^2 + x + y - (y^2 - 1) = x + y + 1$$

At this point $\text{lt}(p) = x$ is not divisible by $xy$ or $y^2$, so it moves into the remainder: $r = x + y + 1$.

S-Polynomials

The S-polynomial is the core building block of Gröbner basis algorithms.

Definition. Let $f, g$ be nonzero polynomials and $\gamma = \text{lcm}(\text{lm}(f), \text{lm}(g))$ (componentwise maximum of the exponent vectors). The S-polynomial of $f$ and $g$ is

$$S(f, g) = \frac{\gamma}{\text{lt}(f)} \cdot f - \frac{\gamma}{\text{lt}(g)} \cdot g = \frac{x^\gamma}{\text{lm}(f)} \cdot f - \frac{x^\gamma}{\text{lm}(g)} \cdot g$$

The intuition behind the S-polynomial is "canceling the leading terms of $f$ and $g$". The Buchberger algorithm repeatedly constructs S-polynomials and reduces them until all S-polynomials reduce to zero — the resulting polynomial set is then a Gröbner basis.

Dickson's Lemma

Dickson's lemma is a finite-generation theorem for monomial ideals and the foundation of Hilbert's basis theorem.

Lemma (Dickson). Every subset $S$ of $\mathbb{N}^n$ has a finite set of "minimal elements" $M \subseteq S$ such that for every $\alpha \in S$ there exists $\beta \in M$ with $\beta \leq \alpha$ (componentwise).

Equivalent statement: every ideal of $\mathbb{F}[x_1, \ldots, x_n]$ generated by monomials is generated by finitely many monomials.

Intuition: In $\mathbb{N}^n$, a "downward-closed" set can only be generated by finitely many "minimal elements". This is analogous to well-ordering in $\mathbb{N}$, but generalized to higher dimensions.

Hilbert's Basis Theorem

Theorem (Hilbert's basis theorem). Every ideal $I$ of $\mathbb{F}[x_1, \ldots, x_n]$ is finitely generated. That is, there exist $f_1, \ldots, f_s \in I$ such that $I = \langle f_1, \ldots, f_s \rangle$.

Proof sketch: Let $J = \langle f_1, \ldots, f_s \rangle$. Consider the leading-term ideal $L(I) = \langle \text{lm}(f) : f \in I \rangle$. By Dickson's lemma, $L(I) = \langle \text{lm}(f_1), \ldots, \text{lm}(f_s) \rangle$, hence $L(J) \supseteq L(I)$. If $J \subsetneq I$, pick $f \in I \setminus J$ whose leading monomial $\text{lm}(f)$ is minimal with respect to $\succ$. Since $\text{lm}(f) \in L(I) \subseteq L(J)$, the defining property of monomial ideals yields some $f_i$ with $\text{lm}(f_i) \mid \text{lm}(f)$; eliminating the leading term of $f$ with $f_i$ gives $f' = f - c, \mathbf{x}^\gamma f_i \in I \setminus J$ with $\text{lm}(f') \prec \text{lm}(f)$ — contradicting the minimality of $\text{lm}(f)$ (well-ordering forbids infinite descending chains). Hence $J = I$.

Significance: Hilbert's basis theorem guarantees the existence of Gröbner bases — the Gröbner basis of every ideal is a finite set. The Buchberger algorithm further provides a constructive proof.

Implementation in oCAS

Dense Univariate Polynomials

DenseUnivariatePolynomial<D> stores the coefficients from the constant term to the leading coefficient in one contiguous vector:

#![allow(unused)]
fn main() {
pub struct DenseUnivariatePolynomial<D: Domain> {
    coeffs: Vec<D::Element>,  // [a0, a1, ..., an]
    domain: D,
}
}

Design decisions:

• Trailing-zero trimming: trailing zero coefficients are removed automatically at construction; the zero polynomial is represented by the empty vector
• Inlined coefficient domain: the domain field is stored inside the polynomial, avoiding the need to pass it to every operation
• Polynomial type parameter: the D: Domain generic allows a unified implementation over the integer ring $\mathbb{Z}$, the rational field $\mathbb{Q}$, finite fields $\mathbb{F}_p$, and so on

Multiplication strategies:

Note: the generic mul takes one of the first two rows (Karatsuba/Schoolbook; the threshold KARATSUBA_THRESHOLD = 32 is applied to the number of coefficients, i.e. degree $\geq 31$). The NTT is enabled through DenseUnivariatePolynomial<FiniteField>::mul_ntt, which internally checks NTT_THRESHOLD = 256 (number of coefficients) and whether the prime is NTT-friendly, and otherwise falls back to Karatsuba/Schoolbook.

The core idea of Karatsuba is to split the polynomials at the midpoint $m = n/2$:

$$a = a_0 + a_1 x^m, \quad b = b_0 + b_1 x^m$$

The product is computed via three half-size multiplications (instead of four):

$$z_0 = a_0 b_0, \quad z_2 = a_1 b_1, \quad z_1 = (a_0 + a_1)(b_0 + b_1) - z_0 - z_2$$

$$a \cdot b = z_0 + z_1 x^m + z_2 x^{2m}$$

EuclideanDomain methods (available when $D: \text{EuclideanDomain}$):

• div_rem(&self, divisor) — division with remainder, returns Option<(quotient, remainder)>
• gcd(&self, other) — polynomial GCD (via a pseudo-remainder PRS chain)
• extended_gcd_poly(&self, other) — extended GCD, returns $(g, s, t)$ with $s \cdot f + t \cdot g = \text{gcd}(f, g)$
• content() — the content (GCD of all coefficients)
• primitive_part() — the primitive part $f / \text{content}(f)$
• square_free_factorization() — square-free factorization
• resultant(&self, other) — the resultant (Brown's PRS algorithm)
• pow(n) — fast exponentiation (repeated squaring)
• p_adic_expansion(p) — the $p$-adic expansion

Univariate polynomial evaluation uses Horner's rule, in $O(n)$ time:

$$f(x) = a_0 + x(a_1 + x(a_2 + \cdots + x \cdot a_n))$$

#![allow(unused)]
fn main() {
// Horner's method
let mut result = domain.zero();
for coeff in self.coeffs.iter().rev() {
    result = domain.mul(&result, x);
    result = domain.add(&result, coeff);
}
}

Sparse Multivariate Polynomials

SparseMultivariatePolynomial<D, O> stores only nonzero terms, mapping exponent vectors to coefficients with a HashMap:

#![allow(unused)]
fn main() {
pub struct SparseMultivariatePolynomial<D: Domain, O: MonomialOrder = Grevlex> {
    terms: HashMap<SmallVec<[usize; 4]>, D::Element>,
    domain: D,
    n_vars: usize,
    pub order: O,
}
}

Design points:

• Exponent vectors: SmallVec<[usize; 4]> — stored inline for small variable counts (no heap allocation for ≤ 4 variables), spilling to the heap for large variable counts
• Default order: O = Grevlex — the most commonly used order for Gröbner basis computations, since it produces the smallest intermediate expressions
• Order as a type parameter: the monomial order is determined at compile time, a zero-cost abstraction. Lex, Grlex, Grevlex are zero-sized types (ZSTs) occupying no runtime space; WeightOrder, MatrixOrder, BlockOrder carry runtime configuration

The MonomialOrder trait:

#![allow(unused)]
fn main() {
pub trait MonomialOrder: Clone + PartialEq + Eq + Debug + Default {
    fn cmp(&self, lhs: &[usize], rhs: &[usize]) -> std::cmp::Ordering;
}
}

The single method cmp compares two exponent vectors. The implementations for each order:

#![allow(unused)]
fn main() {
// Lexicographic order: compare exponent vectors directly
impl MonomialOrder for Lex {
    fn cmp(&self, lhs: &[usize], rhs: &[usize]) -> Ordering {
        lhs.cmp(rhs)
    }
}

// Graded reverse lexicographic: total degree first (descending), then reverse lex
impl MonomialOrder for Grevlex {
    fn cmp(&self, lhs: &[usize], rhs: &[usize]) -> Ordering {
        let deg_lhs: usize = lhs.iter().sum();
        let deg_rhs: usize = rhs.iter().sum();
        deg_rhs.cmp(&deg_lhs)
            .then_with(|| rhs.iter().rev().cmp(lhs.iter().rev()))
    }
}

// Graded lexicographic: total degree first (descending), then lex
impl MonomialOrder for Grlex {
    fn cmp(&self, lhs: &[usize], rhs: &[usize]) -> Ordering {
        let deg_lhs: usize = lhs.iter().sum();
        let deg_rhs: usize = rhs.iter().sum();
        deg_rhs.cmp(&deg_lhs)
            .then_with(|| lhs.cmp(rhs))
    }
}
}

Implementation detail: deg_rhs.cmp(&deg_lhs) rather than deg_lhs.cmp(&deg_rhs) — because in Rust's Ordering, Less means "comes first", and we need the higher degree to come first (i.e. Less), so we compare deg_rhs against deg_lhs. Similarly, in Grevlex, rhs.iter().rev().cmp(lhs.iter().rev()) implements the "reverse" lexicographic order.

Multivariate division is implemented via reduce(&self, basis: &[Self]):

#![allow(unused)]
fn main() {
pub fn reduce(&self, basis: &[Self]) -> Self {
    let mut remainder = self.clone();
    let mut result = self.zero();

    // Cache each basis element's leading term.
    let basis_lts: Vec<_> = basis
        .iter()
        .filter_map(|g| g.leading_term().map(|(e, c)| (g, e.clone(), c.clone())))
        .collect();

    let max_iter = 10000;
    for _ in 0..max_iter {
        if remainder.is_zero() {
            break;
        }
        let (rm, rc) = match remainder.leading_term() {
            Some((e, c)) => (e, c),
            None => break,
        };

        let mut reduced = false;
        for (g, lm, lc) in &basis_lts {
            // lm | rm (componentwise rm[i] ≥ lm[i])
            if monomial_divides(&rm, lm) {
                // compute the quotient monomial
                let qm: SmallVec<[usize; 4]> =
                    rm.iter().zip(lm.iter()).map(|(a, b)| a - b).collect();
                let qc = match self.domain.div(&rc, lc) {
                    Some(q) => q,
                    None => break,
                };
                remainder = remainder.sub(&g.mul_monomial(&qm).mul_scalar(&qc));
                reduced = true;
                break;
            }
        }

        if !reduced {
            result.terms.insert(rm, rc);
            remainder.terms.remove(&rm);
        }
    }
    result
}
}

Helper functions (monomial operations):

#![allow(unused)]
fn main() {
// whether x^b divides x^a (componentwise a[i] ≥ b[i])
pub fn monomial_divides(a: &[usize], b: &[usize]) -> bool

// least common multiple monomial (componentwise max)
pub fn monomial_lcm(a: &[usize], b: &[usize]) -> SmallVec<[usize; 4]>

// whether two monomials are coprime (no common variable)
pub fn monomial_are_coprime(a: &[usize], b: &[usize]) -> bool
}

Dense vs. Sparse: A Selection Guide

Rule of thumb: use the dense representation for univariate polynomials; use the sparse representation for two or more variables. Even a multivariate polynomial with only a few nonzero terms (such as $x^{100} + y^{100}$) needs only two stored terms in the sparse representation, whereas the dense representation would require a $100 \times 100$ coefficient array.

Advanced Topics

Equivalence and Unification of Monomial Orders

Every standard monomial order can be represented uniformly as a matrix order. For $n$ variables:

• Lex $=$ $M = I_n$ (the identity matrix)
• Grlex $=$ the first row all ones, the remaining rows the lexicographic unit vectors in order ($e_1, e_2, \ldots, e_n$ — total degree first, then compare components left to right)
• Grevlex $=$ the first row all ones, the remaining rows the negative reverse-lexicographic unit vectors ($-e_n, -e_{n-1}, \ldots, -e_1$ — total degree first, then compare right to left, the smaller one being greater)

The elimination order constructed by MatrixOrder::elimination_order(k, n) is equivalent to a BlockOrder where the first $k$ variables use Lex and the rest use Grevlex, but the matrix form is more concise.

Limitations of Division

One important limitation of multivariate division with remainder: the remainder depends on the order of the divisors. For example, dividing $f$ by $(g_1, g_2)$ and by $(g_2, g_1)$ may produce different remainders. The introduction of Gröbner bases precisely solves this problem — division by a Gröbner basis yields a unique remainder.

Polynomials over the Integers

When the coefficient ring is $\mathbb{Z}$ (rather than a field), division with remainder needs adjustment. The div_rem of DenseUnivariatePolynomial<IntegerDomain> implements pseudo-division by performing integer division with remainder on the leading coefficients. Concretely, for $f = q \cdot g + r$, the coefficients of $q$ and $r$ may be larger than those of $f$, because division in $\mathbb{Z}$ is not always exact. GCD computation instead uses a pseudo-remainder sequence (PRS) to avoid fraction explosion; for very large integer coefficients the modular GCD can be used instead (gcd/modular.rs, Brown's algorithm). The subresultant PRS is used for resultant computation (resultant.rs).

References

1. Cox, D., Little, J., O'Shea, D. Ideals, Varieties, and Algorithms (4th ed.). Springer, 2015.

   • Chapter 1: basic properties of polynomial rings
   • Chapter 2: introduction to Gröbner bases and the Buchberger algorithm

2. Gathen, J. von zur, Gerhard, J. Modern Computer Algebra (3rd ed.). Cambridge University Press, 2013.

   • Chapter 6: polynomial multiplication algorithms (Karatsuba, FFT, NTT)
   • Chapter 21: multivariate polynomial GCD

3. Adams, W. W., Loustaunau, P. An Introduction to Gröbner Bases. AMS, 1994.

   • Chapter 1: monomial orders and multivariate division

See also

• Gröbner Basis Theory — the solution to the non-uniqueness of division
• Polynomial GCD and Factorization — univariate and multivariate GCD algorithms
• Finite Fields and Modular Arithmetic — polynomial arithmetic over finite fields
• Linear Algebra — Bareiss's fraction-free determinant and Gaussian elimination
• Rust API: Polynomials — the complete API of DenseUnivariatePolynomial and SparseMultivariatePolynomial
• Rust API: Coefficient Domains — the Domain and EuclideanDomain traits