CS 487: Introduction to Symbolic Computation

Armin Jamshidpey

Estimated study time: 1 hr 1 min

Table of contents

Sources and References

Primary textbook — J. von zur Gathen & J. Gerhard, Modern Computer Algebra (3rd ed., Cambridge University Press, 2013)

Supplementary texts — K.O. Geddes, S.R. Czapor & G. Labahn, Algorithms for Computer Algebra (Springer, 1992); D. Cox, J. Little & D. O’Shea, Ideals, Varieties, and Algorithms (4th ed., Springer, 2015)

Online resources — CS 487/687 handouts, University of Waterloo (student.cs.uwaterloo.ca/~cs487/handouts.shtml); MIT OCW 18.783 Elliptic Curves; lecture notes from Shoup’s A Computational Introduction to Number Theory and Algebra

Chapter 1: Polynomials and Their Representations

Symbolic computation distinguishes itself from numerical computation in one fundamental way: it operates on exact algebraic objects rather than floating-point approximations. When a numerical algorithm computes $\sqrt{2} \approx 1.41421356\ldots$, it introduces rounding error at every step. A symbolic algorithm, by contrast, manipulates the object $\sqrt{2}$ — or equivalently, the polynomial $x^2 - 2$ whose root it is — without ever losing precision. This philosophical distinction drives everything in this course.

The central objects of symbolic computation are polynomials. A polynomial $f \in R[x]$ over a ring $R$ is a formal sum

\[ f = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0, \]

where $a_i \in R$ are the coefficients and $n = \deg(f)$ is the degree of $f$ (the largest index $i$ with $a_i \neq 0$). The leading coefficient is $\text{lc}(f) = a_n$, and if $\text{lc}(f) = 1$ we say $f$ is monic.

The most important coefficient rings in this course are $\mathbb{Z}$ (the integers), $\mathbb{Q}$ (the rationals), $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ (the field of $p$ elements for a prime $p$), and $\mathbb{F}_q$ (a finite field of prime-power order $q = p^k$). Each choice of ring brings different algorithmic challenges. Over $\mathbb{Z}$, coefficients can grow without bound — a phenomenon called coefficient explosion — making cost analysis subtle. Over $\mathbb{F}_p$, all arithmetic is cheap and modular, which is why many algorithms reduce to computations over finite fields and then lift.

Representing Polynomials

There are two standard data structures for polynomials.

Definition (Dense representation): A polynomial $f = \sum_{i=0}^{n} a_i x^i$ of degree $n$ is stored as the list $[a_0, a_1, \ldots, a_n]$ of all $n+1$ coefficients, including those equal to zero.

The dense representation is natural when the polynomial is “full” — when most coefficients are nonzero. Addition of two degree-$n$ polynomials stored densely takes $O(n)$ ring operations. Scalar multiplication is also $O(n)$. The weakness of dense storage emerges for sparse polynomials: consider $f = x^{1000} + 1$, which has degree 1000 but only two nonzero terms. Storing it densely requires 1001 entries, whereas it needs only 2.

Definition (Sparse representation): A polynomial $f = \sum_{i \in S} a_i x^i$ with support $S = \{i : a_i \neq 0\}$ is stored as a list of pairs $\{(i, a_i) : i \in S\}$, sorted by exponent.

For a polynomial with $t$ nonzero terms (a $t$-sparse polynomial), the sparse representation uses $O(t)$ space regardless of the degree. In practice, computer algebra systems like Maple use sparse representations internally. Throughout these notes we measure polynomial arithmetic in terms of the number of nonzero terms or the degree as appropriate to the context.

Basic Arithmetic

Addition of two polynomials, whether dense or sparse, is straightforward. The interesting operation is multiplication. Given $f = \sum_{i=0}^{m} a_i x^i$ and $g = \sum_{j=0}^{n} b_j x^j$, their product is

\[ (fg)_k = \sum_{i+j=k} a_i b_j. \]

The product has degree $m + n$ and is computed as a convolution of the coefficient sequences. Naively, each of the $O(m + n)$ output coefficients requires $O(\min(m,n))$ multiplications, giving:

Theorem (Naive multiplication complexity): The naive algorithm for multiplying polynomials of degrees $m$ and $n$ requires $O(mn)$ ring operations.
Proof sketch. There are $(m+1)(n+1)$ products $a_i b_j$ to compute and accumulate.

For polynomials of equal degree $n$, naive multiplication is $O(n^2)$. This quadratic barrier is the central motivation for the fast algorithms in Chapters 2 and 3.

Horner’s Method for Evaluation

A polynomial of degree $n$ has $n+1$ coefficients. Evaluating $f(\alpha)$ naively requires computing $\alpha^k$ for each $k$, which seems to demand $O(n)$ multiplications just for the powers — plus $n$ multiplications of coefficients by powers, totalling roughly $2n$ multiplications and $n$ additions. Horner’s method reduces this to $n$ multiplications and $n$ additions.

Definition (Horner's method): The Horner form of $f = a_n x^n + \cdots + a_0$ is the nested expression \[ f(\alpha) = a_0 + \alpha(a_1 + \alpha(a_2 + \cdots + \alpha(a_{n-1} + \alpha \cdot a_n)\cdots)). \] This is evaluated right-to-left: start with $b_n = a_n$, then $b_k = a_k + \alpha \cdot b_{k+1}$ for $k = n-1, \ldots, 0$, and output $b_0 = f(\alpha)$.

Horner’s method achieves the information-theoretic lower bound of $n$ multiplications for general polynomial evaluation — one cannot do better in an adversarial model. It is the foundation for multi-point evaluation algorithms studied in Chapter 2.

Polynomial Identity Testing

A fundamental algorithmic question is: given two polynomial expressions (perhaps described implicitly as arithmetic circuits), are they identical as polynomials? Expanding them symbolically may be exponentially expensive.

Theorem (Schwartz–Zippel Lemma): Let $f \in R[x_1, \ldots, x_n]$ be a nonzero polynomial of total degree $d$, and let $S \subseteq R$ be a finite set. If we pick $r_1, \ldots, r_n$ independently and uniformly at random from $S$, then \[ \Pr[f(r_1, \ldots, r_n) = 0] \leq \frac{d}{|S|}. \]

This gives a randomized algorithm: evaluate the polynomial at a random point; if the result is nonzero, the polynomial is certainly nonzero; if the result is zero, either the polynomial is identically zero (probability 1) or we were unlucky (probability at most $d/|S|$). By choosing $|S|$ large relative to $d$, we can make the error probability arbitrarily small. Polynomial identity testing is a problem of great theoretical importance, with connections to derandomisation and circuit complexity.

Chapter 2: Evaluation, Interpolation, and Multiplication

Polynomial evaluation and interpolation are dual operations: evaluation maps a polynomial to a sequence of values, while interpolation reconstructs a polynomial from its values. Both operations at multiple points are central to fast multiplication algorithms.

Multi-point Evaluation

The naive approach to evaluating a degree-$n$ polynomial at $n+1$ points applies Horner’s method $n+1$ times, costing $O(n^2)$ operations. The subproduct tree method reduces this.

Definition (Subproduct tree): Given evaluation points $\alpha_0, \ldots, \alpha_{n}$, the subproduct tree is a balanced binary tree whose leaves are the linear polynomials $(x - \alpha_i)$, and each internal node holds the product of its children's polynomials. The root holds $M(x) = \prod_{i=0}^{n}(x - \alpha_i)$.

Computing the subproduct tree requires $O(M(n) \log n)$ operations, where $M(n)$ denotes the cost of multiplying two degree-$n$ polynomials. Once built, multi-point evaluation can be performed by a top-down traversal: at each node with polynomial $m(x)$, reduce $f$ modulo the two child polynomials $m_L(x)$ and $m_R(x)$, then recurse. This yields:

Theorem (Fast multi-point evaluation): Given a polynomial $f$ of degree $n$ and $n+1$ evaluation points, multi-point evaluation can be done in $O(M(n) \log n)$ operations.

Lagrange Interpolation

Given $n+1$ pairs $(\alpha_0, v_0), \ldots, (\alpha_n, v_n)$ with the $\alpha_i$ distinct, there is a unique polynomial $f$ of degree at most $n$ with $f(\alpha_i) = v_i$.

Theorem (Lagrange interpolation formula): The unique interpolating polynomial is \[ f(x) = \sum_{i=0}^{n} v_i \prod_{j \neq i} \frac{x - \alpha_j}{\alpha_i - \alpha_j}. \]

The naive construction evaluates each of the $n+1$ basis polynomials $\ell_i(x) = \prod_{j \neq i}(x - \alpha_j) / (\alpha_i - \alpha_j)$ in $O(n)$ time, totalling $O(n^2)$. Fast interpolation using the subproduct tree also achieves $O(M(n) \log n)$.

The Patterson–Stockmeyer Algorithm

Horner’s method evaluates a degree-$n$ polynomial using exactly $n$ multiplications. Can we do better for a single evaluation point? The answer is yes, if we allow precomputation or exploit the algebraic structure of the polynomial.

The Patterson–Stockmeyer algorithm addresses optimal evaluation of a polynomial $f$ of degree $n$ where the coefficients are given but the evaluation point $x$ is “fresh” (so precomputing powers of $x$ counts). The key idea is to write $n \approx s \cdot t$ for parameters $s \approx \sqrt{n}$ and express:

\[ f(x) = \sum_{i=0}^{t} Q_i(x) \cdot (x^s)^i, \]

where each $Q_i$ has degree less than $s$. This is a polynomial in the variable $y = x^s$ with polynomial coefficients in $x$. We precompute $x, x^2, \ldots, x^{s-1}$ and $y, y^2, \ldots, y^{t-1}$ (about $s + t \approx 2\sqrt{n}$ multiplications), then evaluate each $Q_i(x)$ using precomputed powers (few multiplications each) and finally evaluate the outer polynomial in $y$ using Horner.

Theorem (Patterson–Stockmeyer): A polynomial of degree $n$ can be evaluated at a single point using $O(\sqrt{n})$ multiplications (plus $O(n)$ additions).

This beats Horner’s $n$ multiplications by a factor of $\sqrt{n}$. The result is asymptotically optimal in the additive chain model for polynomial evaluation with arbitrary coefficients.

Polynomial Multiplication via Evaluation and Interpolation

The bridge between polynomial multiplication and the DFT is the following observation. To multiply $f$ and $g$ of degree at most $n$, we need to determine the $2n+1$ coefficients of $fg$. By interpolation, it suffices to know the values of $fg$ at $2n+1$ points. But $(fg)(\alpha) = f(\alpha) \cdot g(\alpha)$, so:

Evaluate: compute $f(\alpha_i)$ and $g(\alpha_i)$ for $i = 0, \ldots, 2n$.
Pointwise multiply: compute $f(\alpha_i) \cdot g(\alpha_i)$ for each $i$ — this is $O(n)$ operations.
Interpolate: reconstruct $fg$ from the $2n+1$ values.

The evaluation and interpolation steps dominate. With naive methods they cost $O(n^2)$, giving no improvement. The breakthrough of the FFT is that when the evaluation points are chosen to be roots of unity, the evaluation and interpolation steps can each be done in $O(n \log n)$.

Chapter 3: The Discrete Fourier Transform

The Discrete Fourier Transform (DFT) is the cornerstone of fast polynomial multiplication. Its key insight is that evaluation at roots of unity admits a recursive divide-and-conquer decomposition.

Roots of Unity and the DFT

Definition (Primitive root of unity): In a ring $R$, an element $\omega$ is a primitive $n$th root of unity if $\omega^n = 1$ and $\omega^k \neq 1$ for $0 < k < n$. We require that $n$ is invertible in $R$.

Over $\mathbb{C}$, the primitive $n$th roots of unity are $e^{2\pi i k/n}$ for $\gcd(k,n) = 1$. The standard choice is $\omega_n = e^{2\pi i/n}$.

Definition (DFT): Given a sequence $(a_0, a_1, \ldots, a_{n-1})$ in a ring $R$ with a primitive $n$th root of unity $\omega$, the DFT of the sequence is the sequence $(\hat{a}_0, \hat{a}_1, \ldots, \hat{a}_{n-1})$ where \[ \hat{a}_k = \sum_{j=0}^{n-1} a_j \omega^{jk}, \quad k = 0, 1, \ldots, n-1. \]

Observe that $\hat{a}_k = f(\omega^k)$ where $f = \sum_{j=0}^{n-1} a_j x^j$. Thus the DFT of the coefficient sequence of $f$ is exactly the evaluation of $f$ at all $n$ roots of unity simultaneously.

The DFT can be represented as multiplication by the Vandermonde matrix $V_n$ with entries $(V_n)_{k,j} = \omega^{kj}$. The inverse DFT uses the fact that $V_n \cdot \overline{V_n} = n \cdot I$, so $V_n^{-1} = \frac{1}{n} \overline{V_n}$, giving:

\[ a_j = \frac{1}{n} \sum_{k=0}^{n-1} \hat{a}_k \omega^{-jk}. \]

Naive matrix-vector multiplication computes the DFT in $O(n^2)$ operations. The FFT reduces this dramatically.

The Fast Fourier Transform

The Cooley–Tukey FFT (1965, though the algorithm was known to Gauss) applies when $n = 2^m$ is a power of 2. It exploits the following factorisation.

Theorem (Cooley–Tukey FFT): For $n = 2m$, the $n$-point DFT can be computed from two $m$-point DFTs as follows. Split $f(x) = f_{\text{even}}(x^2) + x \cdot f_{\text{odd}}(x^2)$ where $f_{\text{even}}(y) = \sum_{j=0}^{m-1} a_{2j} y^j$ and $f_{\text{odd}}(y) = \sum_{j=0}^{m-1} a_{2j+1} y^j$. Then for $k = 0, \ldots, m-1$: \[ f(\omega^k) = f_{\text{even}}(\omega^{2k}) + \omega^k \cdot f_{\text{odd}}(\omega^{2k}), \] \[ f(\omega^{k+m}) = f_{\text{even}}(\omega^{2k}) - \omega^k \cdot f_{\text{odd}}(\omega^{2k}). \] Since $\omega^2$ is a primitive $m$th root of unity, both inner DFTs are $m$-point DFTs.
Proof sketch. Direct substitution using $\omega^{k+m} = -\omega^k$ (which holds because $\omega^n = 1$ and $n = 2m$).

The recurrence $T(n) = 2T(n/2) + O(n)$ solves to $T(n) = O(n \log n)$. This is the famous butterfly network structure: each level of the recursion does $O(n)$ work (twiddle factor multiplications $\omega^k$ and additions), and there are $\log_2 n$ levels.

Example (4-point FFT): Let $n = 4$, $\omega = i$ (a primitive 4th root of unity over $\mathbb{C}$). Given $(a_0, a_1, a_2, a_3)$, split into evens $(a_0, a_2)$ and odds $(a_1, a_3)$. Compute 2-point DFTs:

Even DFT: $\hat{E}_0 = a_0 + a_2$, $\hat{E}_1 = a_0 - a_2$.
Odd DFT: $\hat{O}_0 = a_1 + a_3$, $\hat{O}_1 = a_1 - a_3$.

Combine: $\hat{a}_k = \hat{E}_k + i^k \hat{O}_k$ and $\hat{a}_{k+2} = \hat{E}_k - i^k \hat{O}_k$ for $k = 0, 1$. This requires 2 complex multiplications (by $i^0 = 1$ and $i^1 = i$) plus 8 additions, compared to 16 multiplications and 12 additions for the naive DFT.

Polynomial Multiplication via FFT

To multiply polynomials $f, g$ of degree at most $n$ using the FFT:

Zero-pad both polynomials to length $N = 2^{\lceil \log_2(2n+1) \rceil}$ (the next power of 2 above $2n$).
Compute $\hat{f} = \text{DFT}_N(f)$ and $\hat{g} = \text{DFT}_N(g)$ — each costs $O(N \log N)$.
Pointwise product: $\hat{h}_k = \hat{f}_k \cdot \hat{g}_k$ for $k = 0, \ldots, N-1$ — costs $O(N)$.
Inverse DFT: $h = \text{DFT}_N^{-1}(\hat{h})$ — costs $O(N \log N)$.

Since $N = O(n)$, the total cost is $O(n \log n)$, a dramatic improvement over the naive $O(n^2)$.

Theorem (FFT multiplication): Two polynomials of degree $n$ can be multiplied in $O(n \log n)$ arithmetic operations using the FFT, provided the coefficient ring contains a primitive $N$th root of unity for a suitable $N = O(n)$.

The caveat about roots of unity is important. Over $\mathbb{C}$, primitive roots of unity always exist, but we are working with floating-point approximations, introducing rounding errors. Over $\mathbb{Z}$, no primitive roots of unity exist in general. The fix for exact integer or polynomial arithmetic uses number theoretic transforms (NTT): work modulo a prime $p$ of the form $p = c \cdot 2^k + 1$ (a Fermat prime or NTT prime), which has a primitive $2^k$th root of unity modulo $p$. By choosing $p > (n+1) \cdot (\max |a_i|)^2$, no information is lost modulo $p$.

Alternatively, for $\mathbb{Z}[x]$ multiplication, one can evaluate at many primes, do pointwise NTT multiplication modulo each prime, and use the CRT (Chapter 5) to recover the result over $\mathbb{Z}$.

The DFT in Finite Fields

Over $\mathbb{F}_q$, the multiplicative group $\mathbb{F}_q^*$ is cyclic of order $q-1$. If $n \mid (q-1)$, then primitive $n$th roots of unity exist in $\mathbb{F}_q$. This makes NTT-based polynomial multiplication available over finite fields whenever the size of the transform divides $q-1$. This is used heavily in polynomial factoring algorithms (Chapter 8).

Chapter 4: Division, Remainder Sequences, and Newton Iteration

While polynomial multiplication is fundamental, many algorithms require division with remainder and the Euclidean algorithm for polynomial GCDs. These operations lead to the problem of coefficient explosion and motivate algebraic Newton iteration for fast inversion.

Euclidean Division

Theorem (Division with remainder): Let $R$ be a field and $f, g \in R[x]$ with $g \neq 0$. There exist unique polynomials $q, r \in R[x]$ such that $f = q \cdot g + r$ and $\deg(r) < \deg(g)$. We call $q$ the quotient and $r$ the remainder, written $r = f \bmod g$.

Over a field, long division of polynomials proceeds exactly as integer long division. The cost of computing $q$ and $r$ when $\deg(f) = m$ and $\deg(g) = n \leq m$ is $O((m-n+1) \cdot n)$ field operations — which is $O(n^2)$ in the worst case.

Over $\mathbb{Z}[x]$, exact division requires the leading coefficient of $g$ to divide the relevant coefficient of $f$ at each step. To avoid this issue, one introduces pseudo-division.

Definition (Pseudo-division): For $f, g \in \mathbb{Z}[x]$ with $\deg(f) = m \geq n = \deg(g)$ and $\text{lc}(g) = b$, the pseudo-remainder is the remainder of $b^{m-n+1} f$ divided by $g$ in $\mathbb{Q}[x]$, and it lies in $\mathbb{Z}[x]$. We write $\text{prem}(f, g) = b^{m-n+1} f \bmod g$.

Pseudo-division guarantees integer coefficients at the cost of introducing powers of the leading coefficient, which can cause coefficient growth.

The Euclidean Algorithm for Polynomials

The polynomial GCD problem asks for the highest-degree monic polynomial $d$ dividing both $f$ and $g$. The Euclidean algorithm applies the recurrence:

\[ \gcd(f, g) = \gcd(g, f \bmod g), \]

terminating when the remainder is zero. The sequence of remainders $r_0 = f, r_1 = g, r_2, \ldots, r_k = 0$ with $\gcd(f,g) = r_{k-1}$ is called the polynomial remainder sequence (PRS).

Over a field, this algorithm runs in $O(n^2)$ operations for degree-$n$ inputs. The difficulty over $\mathbb{Z}$ is that the pseudo-remainders $r_i$ may have exponentially growing coefficients — the coefficient explosion problem.

Example (Coefficient explosion): Consider $f = x^4 + x^3 + x^2 + x + 1$ and $g = x^3 + 2x^2 + 3x + 4$ in $\mathbb{Z}[x]$. The pseudo-remainder sequence can produce intermediate polynomials whose coefficients grow exponentially in the degree of the inputs, even though the final GCD has small coefficients.

The solution is to use subresultant pseudo-remainder sequences, which control coefficient growth to polynomial size, or to use modular GCD algorithms (Chapter 6) that avoid intermediate coefficient growth entirely.

Algebraic Newton Iteration

Newton’s method for finding roots of a function $F$ iterates $x_{k+1} = x_k - F(x_k)/F'(x_k)$ with quadratic convergence: the number of correct digits doubles at each step. A powerful algebraic generalisation applies this idea in polynomial rings.

The problem: given $f \in R[x]$, compute a polynomial $g$ such that $g \equiv f^{-1} \pmod{x^n}$, i.e., $fg \equiv 1 \pmod{x^n}$. (We assume $f(0) \neq 0$ is a unit in (R.)

Definition (Newton iteration for polynomial inversion): Given $g_k$ with $f g_k \equiv 1 \pmod{x^{2^k}}$, the Newton refinement is \[ g_{k+1} = 2g_k - f \cdot g_k^2 \pmod{x^{2^{k+1}}}. \] Starting from $g_0 = f(0)^{-1}$ in $R$, this procedure doubles the number of correct terms at each step.

The correctness follows by a simple calculation: let $e_k = 1 - fg_k$ (the “error”). Then $e_{k+1} = 1 - fg_{k+1} = 1 - f(2g_k - fg_k^2) = (1 - fg_k)^2 = e_k^2$. Since $e_k \equiv 0 \pmod{x^{2^k}}$, we get $e_{k+1} \equiv 0 \pmod{x^{2^{k+1}}}$ — quadratic convergence in the 2-adic sense.

Theorem (Cost of Newton inversion): Computing $f^{-1} \pmod{x^n}$ via Newton iteration requires $O(M(n))$ operations, where $M(n)$ is the cost of multiplying two degree-$n$ polynomials.

The proof uses the geometric series bound: the total work across all iterations is $M(2^0) + M(2^1) + \cdots + M(2^k) = O(M(2^k)) = O(M(n))$ because $M(n) = O(n \log n)$ grows faster than a geometric series.

Newton iteration is used to compute polynomial inverses modulo $x^n$ (needed for fast division), to solve systems of polynomial equations, and as a subroutine in Hensel lifting (Chapter 8).

Chapter 5: The Chinese Remainder Algorithm

The Chinese Remainder Theorem is one of the most versatile tools in symbolic computation. It states that a system of congruences with pairwise coprime moduli has a unique solution modulo their product. Algorithmically, it allows us to split a hard computation over $\mathbb{Z}$ into many easy computations over $\mathbb{Z}/m_i\mathbb{Z}$, work in parallel, then reconstruct the answer.

CRT for Integers

Theorem (Chinese Remainder Theorem): Let $m_1, \ldots, m_k$ be pairwise coprime positive integers with $M = m_1 \cdots m_k$. For any $r_1, \ldots, r_k$ with $0 \leq r_i < m_i$, there is a unique integer $u$ with $0 \leq u < M$ such that $u \equiv r_i \pmod{m_i}$ for all $i$.

The constructive proof uses Bezout coefficients: since $\gcd(m_i, M/m_i) = 1$, there exist $s_i$ with $s_i(M/m_i) \equiv 1 \pmod{m_i}$. Setting $u = \sum_i r_i \cdot s_i \cdot (M/m_i) \pmod{M}$ gives the unique solution.

Garner’s algorithm provides a more numerically stable mixed-radix representation. Instead of computing large partial products $M/m_i$, it builds up a representation $u = c_0 + c_1 m_1 + c_2 m_1 m_2 + \cdots + c_{k-1} m_1 \cdots m_{k-1}$ where $0 \leq c_i < m_i$. The coefficients $c_i$ are determined by solving a triangular system over the small moduli $m_1, \ldots, m_k$.

Example (CRT reconstruction): Suppose we know that some integer $u$ (representing a result we care about) satisfies $u \equiv 3 \pmod{5}$, $u \equiv 1 \pmod{7}$, $u \equiv 6 \pmod{11}$. By CRT, $u$ is unique modulo $5 \cdot 7 \cdot 11 = 385$. If we additionally know that $|u| < 192$, we can uniquely recover $u \in \mathbb{Z}$ — the answer is $u = -57$.

CRT for Polynomials

The same idea applies to polynomials over a field $F$.

Theorem (Polynomial CRT): Let $m_1(x), \ldots, m_k(x) \in F[x]$ be pairwise coprime, $M(x) = \prod m_i(x)$. For any $r_1(x), \ldots, r_k(x)$ with $\deg(r_i) < \deg(m_i)$, there is a unique polynomial $u(x)$ with $\deg(u) < \deg(M)$ such that $u \equiv r_i \pmod{m_i}$ for all $i$.

When the moduli are linear, $m_i(x) = x - \alpha_i$, the “residues” are just the values $r_i = u(\alpha_i)$, and CRT reconstruction is precisely Lagrange interpolation. Thus the CRT unifies interpolation and the classical number-theoretic CRT.

The Modular Algorithm Paradigm

The modular algorithm paradigm is a general strategy for computing in $\mathbb{Z}[x]$:

Choose a set of primes $p_1, \ldots, p_k$ such that their product $M = p_1 \cdots p_k$ exceeds the bound on the coefficients of the answer.
For each prime $p_i$, reduce the input to $\mathbb{F}_{p_i}[x]$ and perform the computation there (cheaply, since coefficients are bounded by $p_i$).
Use CRT to reconstruct the answer in $\mathbb{Z}[x]$ from its reductions modulo each $p_i$.
Recover the result over $\mathbb{Z}$ by rational number reconstruction or by checking that coefficients fall in a symmetric interval $(-M/2, M/2]$.

This paradigm underlies the modular GCD algorithm (Chapter 6), modular determinant computation (Chapter 7), and polynomial factoring (Chapter 8). Its efficiency depends critically on how many primes are needed — i.e., on coefficient bounds for the answer.

Chapter 6: Greatest Common Divisors

The polynomial GCD is among the most important operations in computer algebra. It arises in simplification of rational functions, solving polynomial systems, testing irreducibility, and many other contexts. The challenge, as discussed in Chapter 4, is avoiding coefficient explosion when working over $\mathbb{Z}$.

Resultants and the Sylvester Matrix

The resultant of two polynomials provides a powerful tool for eliminating variables and testing common roots.

Definition (Resultant): Let $f = a \prod_{i=1}^{m}(x - \alpha_i)$ and $g = b \prod_{j=1}^{n}(x - \beta_j)$ be polynomials of degrees $m$ and $n$. Their resultant is \[ \text{Res}(f, g) = a^n b^m \prod_{i=1}^{m} \prod_{j=1}^{n} (\alpha_i - \beta_j). \]

The resultant vanishes if and only if $f$ and $g$ have a common root (in the algebraic closure) — equivalently, $\gcd(f, g) \neq 1$. This makes it an algebraic certificate for non-coprimality.

Computationally, the resultant equals the determinant of the Sylvester matrix $S(f,g)$, an $(m+n) \times (m+n)$ matrix built from the coefficients of $f$ and $g$. This gives an algorithm for computing the resultant via Gaussian elimination, but at cost $O(n^3)$ for degree-$n$ inputs.

A more efficient approach uses the subresultant sequence: a sequence of polynomials (\text{Sres}_0(f,g), \text{Sres}_1(f,g), \ldots$ that generalise the remainder sequence and whose entries are the non-trivial subresultants (the square minors of the Sylvester matrix).

Theorem (Subresultant–GCD connection): If $d = \deg(\gcd(f,g))$, then $\text{Sres}_d(f,g)$ is a scalar multiple of $\gcd(f,g)$, and $\text{Sres}_k(f,g) = 0$ for $0 \leq k < d$.

Modular GCD Algorithm

The modular GCD algorithm avoids coefficient explosion by computing the GCD modulo several primes.

The algorithm for $f, g \in \mathbb{Z}[x]$ proceeds as follows:

Compute $d = \gcd(\text{cont}(f), \text{cont}(g))$ (the GCD of contents, where the content is the GCD of the coefficients).
Let $f_0 = f/\text{cont}(f)$ and $g_0 = g/\text{cont}(g)$ (the primitive parts).
Compute a coefficient bound $B$ on the coefficients of the primitive GCD, using Hadamard’s bound.
Choose primes $p_1, p_2, \ldots$ (avoiding primes that divide the leading coefficients) and compute $h_i = \gcd(f_0 \bmod p_i, \; g_0 \bmod p_i)$ in $\mathbb{F}_{p_i}[x]$ using the Euclidean algorithm.
Use CRT to lift the $h_i$ to a candidate $h \in \mathbb{Z}[x]$ with coefficients in $(-M/2, M/2]$ for $M = \prod p_i > 2B$.
Test whether $h \mid f_0$ and $h \mid g_0$ in $\mathbb{Z}[x]$. If so, return $d \cdot h$.

A complication is that the GCD modulo $p$ may have smaller degree than the true GCD (if $p$ divides the leading coefficient of the true GCD) — we call such primes unlucky. The algorithm detects and discards unlucky primes by checking that the degree of $h_i$ matches the expected degree.

Theorem (Correctness of modular GCD): With enough lucky primes, the modular GCD algorithm correctly computes $\gcd(f,g)$ in $\mathbb{Z}[x]$. The number of primes needed is polynomial in $n$ and $\log(\max|a_i|)$.

Chapter 7: Linear Algebra Over Exact Domains

Solving linear systems and computing determinants over $\mathbb{Z}$ or $\mathbb{Q}$ — exact linear algebra — presents challenges not present over floating-point fields. The primary difficulties are coefficient explosion in Gaussian elimination and the need to return exact rational solutions.

Fraction-Free Gaussian Elimination

Standard Gaussian elimination over $\mathbb{Q}$ introduces rational numbers at every step. Over $\mathbb{Z}$, the analogous procedure introduces denominators, causing coefficient growth.

Bareiss’s algorithm performs Gaussian elimination while keeping all entries as integers, using a carefully chosen division at each step that is guaranteed to be exact.

Definition (Bareiss algorithm): Given $A \in \mathbb{Z}^{n \times n}$, define the sequence of matrices $A^{(k)}$ with entries \[ A^{(k)}_{ij} = \frac{A^{(k-1)}_{kk} A^{(k-1)}_{ij} - A^{(k-1)}_{ik} A^{(k-1)}_{kj}}{A^{(k-2)}_{k-1,k-1}} \] for $i, j > k$, starting from $A^{(0)} = A$ and $A^{(-1)}_{00} = 1$. Bareiss's theorem guarantees the division is always exact, and $A^{(n-1)}_{nn} = \det(A)$.

Bareiss’s algorithm avoids fractions and keeps intermediate coefficients bounded by $O(n \cdot \|A\|_\infty^2)$ where $\|A\|_\infty = \max_{i,j} |a_{ij}|$. While better than unchecked fraction growth, this can still be large.

Modular Determinant via CRT

A faster approach uses the modular paradigm: compute $\det(A) \bmod p_i$ for several primes, then reconstruct via CRT. Computing a determinant modulo a prime uses $O(n^3)$ field operations. The number of primes needed is determined by Hadamard’s bound:

Theorem (Hadamard's bound): For $A \in \mathbb{Z}^{n \times n}$, \[ |\det(A)| \leq \prod_{i=1}^{n} \|a_i\|_2 \leq n^{n/2} \|A\|_\infty^n. \]

This bound grows exponentially in $n$, but the number of bits required is only $O(n \log(n \|A\|_\infty))$, which is polynomial. The modular determinant algorithm uses $O(n \log(n \|A\|_\infty))$ primes, and the total work is $O(n^3 \cdot n \log(n\|A\|_\infty))$.

Dixon’s Algorithm for Rational System Solving

Given $Ax = b$ with $A \in \mathbb{Z}^{n \times n}$ nonsingular and $b \in \mathbb{Z}^n$, the solution $x = A^{-1}b$ is a vector of rational numbers. By Cramer’s rule, $x_i = \det(A_i)/\det(A)$ where $A_i$ replaces the $i$th column of $A$ with $b$. This is computable but expensive.

Dixon’s algorithm uses $p$-adic lifting, an algebraic analogue of Newton iteration.

The idea: fix a prime $p$ with $p \nmid \det(A)$. Compute the solution $x^{(0)}$ to $Ax \equiv b \pmod{p}$, then lift to higher powers of $p$:

Compute $x^{(0)} = A^{-1}b \pmod{p}$ (standard linear algebra mod $p$, cost $O(n^3)$).
Compute the residual $r^{(0)} = (b - Ax^{(0)})/p \in \mathbb{Z}^n$.
Compute $x^{(1)} = A^{-1}r^{(0)} \pmod{p}$.
Then $x \equiv x^{(0)} + p \cdot x^{(1)} \pmod{p^2}$.
Iterate: after $k$ steps, we know $x \pmod{p^k}$.

After $O(n \log(n\|A\|_\infty))$ lifting steps, we know the solution modulo a sufficiently large power of $p$ to recover the rational solution via rational number reconstruction (the rational analogue of CRT).

Theorem (Dixon's algorithm complexity): Dixon's algorithm solves $Ax = b$ over $\mathbb{Q}$ in $O(n^3 \cdot n \log(n\|A\|_\infty))$ bit operations, matching the modular determinant bound.

Chapter 8: Polynomial Factoring

Factoring a polynomial $f$ into irreducible factors is a central problem in algebra with wide applications: simplifying algebraic expressions, solving equations, testing primality of polynomials. The algorithms proceed in stages: first factor over a finite field (easier), then lift the factorisation to $\mathbb{Z}$ using Hensel’s lemma.

Factoring over Finite Fields: Berlekamp’s Algorithm

Let $f \in \mathbb{F}_q[x]$ be a squarefree polynomial of degree $n$. Berlekamp’s algorithm finds the factorisation by exploiting the Frobenius endomorphism.

Theorem (Berlekamp's key observation): A polynomial $h \in \mathbb{F}_q[x]$ satisfies $h^q \equiv h \pmod{f}$ if and only if $h$ is a product of one element from each factor of $f$ in $\mathbb{F}_q$. The set of such $h$ forms the Berlekamp subalgebra, a vector space of dimension equal to the number of irreducible factors of $f$.

The condition $h^q \equiv h \pmod{f}$ means $h \pmod{f}$ lies in the null space of the matrix $Q - I$, where $Q$ is the matrix of the $q$-power Frobenius map $h \mapsto h^q \pmod{f}$ expressed in the basis $1, x, \ldots, x^{n-1}$.

Berlekamp’s algorithm:

Compute the $n \times n$ matrix $Q$ (the Berlekamp matrix) whose rows are the coefficient vectors of $x^{iq} \bmod f$ for $i = 0, \ldots, n-1$.
Find a basis $h_1 = 1, h_2, \ldots, h_r$ for the null space of $Q - I$ (dimension $r$ = number of irreducible factors).
For each basis vector $h_j$ and each $s \in \mathbb{F}_q$, compute $\gcd(f, h_j - s)$. These GCDs split $f$.

The algorithm runs in polynomial time: $O(n^3)$ for the linear algebra plus $O(n^2 q)$ GCD computations in the worst case. For large $q$, the GCD step dominates, and probabilistic algorithms are preferred.

Cantor–Zassenhaus Algorithm

The Cantor–Zassenhaus algorithm is a randomised algorithm for equal-degree factorisation over $\mathbb{F}_q$ with $q$ odd.

Definition (Equal-degree factorisation): Given $f = f_1 \cdots f_r$ where all $f_i$ are irreducible of the same degree $d$, compute the individual factors.

The idea exploits the fact that $\mathbb{F}_q[x]/(f)\cong \mathbb{F}_{q^d}^r$ as rings. A random element $t \in \mathbb{F}_q[x]$ of degree less than $\deg(f)$, taken modulo each factor $f_i$, lands in $\mathbb{F}_{q^d}^*$. Since $|\mathbb{F}_{q^d}^*| = q^d - 1$ and the map $t \mapsto t^{(q^d-1)/2}$ in $\mathbb{F}_{q^d}$ is $\pm 1$, roughly half the elements map to $+1$ and half to $-1$. By computing $\gcd(f, t^{(q^d-1)/2} - 1)$, we split $f$ with probability roughly $1 - 2^{1-r}$.

Hensel’s Lemma and Lifting

The transition from factoring over $\mathbb{F}_p$ to factoring over $\mathbb{Z}$ uses Hensel’s lemma, the algebraic analogue of Newton’s method.

Theorem (Hensel's Lemma, univariate): Let $f \in \mathbb{Z}[x]$ and suppose $f \equiv g_0 h_0 \pmod{p}$ with $\gcd(g_0, h_0) = 1$ in $\mathbb{F}_p[x]$. Then for any $k \geq 1$, there exist unique polynomials $g_k, h_k \in \mathbb{Z}[x]$ such that $f \equiv g_k h_k \pmod{p^{2^k}}$, $g_k \equiv g_0 \pmod{p}$, $h_k \equiv h_0 \pmod{p}$, and $\deg(g_k) = \deg(g_0)$.

The lifting is computed iteratively using Newton’s method in the ring $\mathbb{Z}/p^{2^k}\mathbb{Z}[x]$: compute Bezout coefficients $s, t$ with $sg_0 + th_0 \equiv 1 \pmod{p}$, then lift using the corrective terms.

The Berlekamp–Zassenhaus Algorithm

The complete algorithm for factoring $f \in \mathbb{Z}[x]$:

Squarefree decomposition: write $f = \prod_i f_i^i$ where each $f_i$ is squarefree, using $\gcd(f, f')$.
Choose a prime $p$ and factor $f \bmod p$ over $\mathbb{F}_p$ using Berlekamp or Cantor–Zassenhaus.
Lift the factorisation from $\mathbb{F}_p$ to $\mathbb{Z}/p^k\mathbb{Z}$ for sufficiently large $k$ (using Hadamard’s bound to determine $k$).
Try all subsets of lifted factors as potential factors of $f$ over $\mathbb{Z}$.

Step 4 is the bottleneck: if $f \bmod p$ has $r$ factors, there are $2^r$ subsets to try. This is exponential in the number of factors. In the worst case, $r$ can be $\Omega(n)$, making the algorithm exponential.

The LLL algorithm (Lenstra–Lenstra–Lovász, 1982) broke through this exponential barrier, providing polynomial-time factoring over $\mathbb{Z}$ via lattice basis reduction. The idea is to encode the factor-combination problem as finding a short vector in a lattice, which LLL solves in polynomial time. This was a landmark result in algorithmic algebra.

Chapter 9: Gröbner Bases and Ideal Theory

Gröbner bases generalise the Euclidean algorithm and Gaussian elimination to the multivariate setting. They provide a canonical form for polynomial ideals and are the computational backbone of algebraic geometry.

Multivariate Polynomials and Ideals

A multivariate polynomial in $k[x_1, \ldots, x_n]$ (where $k$ is a field) is a finite sum of monomials $c \cdot x_1^{\alpha_1} \cdots x_n^{\alpha_n}$, one for each multi-index $\alpha = (\alpha_1, \ldots, \alpha_n) \in \mathbb{Z}_{\geq 0}^n$.

Definition (Ideal): A subset $I \subseteq k[x_1, \ldots, x_n]$ is an ideal if it is closed under addition and under multiplication by any polynomial in the ring: if $f, g \in I$ then $f + g \in I$, and if $f \in I$ and $h \in k[\mathbf{x}]$ then $hf \in I$.

Given polynomials $f_1, \ldots, f_s$, the ideal they generate is $\langle f_1, \ldots, f_s \rangle = \{h_1 f_1 + \cdots + h_s f_s : h_i \in k[\mathbf{x}]\}$. By the Hilbert basis theorem, every ideal in $k[x_1, \ldots, x_n]$ is finitely generated — a fact equivalent to the Noetherian property of polynomial rings.

Monomial Orderings

To define division and leading terms in the multivariate setting, we need a monomial ordering: a total order $\prec$ on monomials that is compatible with multiplication and has 1 as the smallest element.

Definition (Standard monomial orderings): Three commonly used orderings on $k[x_1, \ldots, x_n]$:

Lexicographic (lex): $x^\alpha \succ_{\text{lex}} x^\beta$ iff the leftmost nonzero entry of $\alpha - \beta$ is positive.
Graded lex (grlex): compare by total degree first, then by lex order.
Graded reverse lex (grevlex): compare by total degree first, then by reverse lex on the rightmost variable.

The choice of ordering matters enormously for the structure and efficiency of Gröbner basis computation. Lexicographic order is ideal for elimination (solving systems by successive substitution), but Gröbner bases in lex order are typically far larger and more expensive to compute than in grevlex.

Multivariate Division

Given a polynomial $f$ and a list of polynomials $F = (f_1, \ldots, f_s)$, the **multivariate division algorithm** reduces \(f$ modulo $F$:

Starting from remainder $r = 0$ and \(p = f$:

While $p \neq 0$: find the first $f_i$ whose leading term divides the leading term of $p$; if found, subtract the appropriate multiple of $f_i$ from $p$; otherwise, move $\text{lt}(p)$ to $r$ and continue.

Unlike univariate division, the remainder depends on the order of the $f_i$ and may not be unique. A Gröbner basis is precisely a generating set for which multivariate division gives a unique remainder.

Gröbner Bases

Definition (Gröbner basis): A finite set $G = \{g_1, \ldots, g_t\} \subseteq I$ is a Gröbner basis for the ideal $I$ with respect to a monomial ordering if $\langle \text{lt}(g_1), \ldots, \text{lt}(g_t) \rangle = \langle \text{lt}(f) : f \in I \rangle$, i.e., the leading term ideal of $G$ equals the leading term ideal of $I$.

Equivalently, $G$ is a Gröbner basis if and only if every polynomial in $I$ reduces to zero modulo $G$, i.e., the division algorithm with $G$ always yields remainder zero for elements of $I$. This makes Gröbner bases the correct analogue of the single generator in the univariate case: in $k[x]$, every ideal is principal and a basis $\{g\}$ is a Gröbner basis because division by $g$ is unique.

Gröbner bases give algorithmic solutions to fundamental ideal-theoretic problems:

Ideal membership: $f \in I$ iff the remainder of $f$ modulo a Gröbner basis of $I$ is zero.
Equality of ideals: $I = J$ iff their reduced Gröbner bases (with respect to the same ordering) are identical.
Variety membership and implicitisation: whether a point lies on a variety, and finding implicit equations.

S-Polynomials and Buchberger’s Algorithm

The key construction is the S-polynomial (syzygy polynomial), which detects and resolves “conflicts” between the leading terms of two generators.

Definition (S-polynomial): For $f, g \in k[\mathbf{x}]$ with $L = \text{lcm}(\text{lt}(f), \text{lt}(g))$, the S-polynomial is \[ S(f, g) = \frac{L}{\text{lt}(f)} \cdot f - \frac{L}{\text{lt}(g)} \cdot g. \]

The S-polynomial is designed so that the leading terms of $f$ and $g$ cancel, potentially revealing cancellation patterns that the original generators miss.

Theorem (Buchberger's criterion): A basis $G = \{g_1, \ldots, g_t\}$ for an ideal $I$ is a Gröbner basis if and only if the remainder of $S(g_i, g_j)$ upon division by $G$ is zero for all $i \neq j$.

Buchberger’s algorithm builds a Gröbner basis by repeatedly checking S-polynomials and adding nonzero remainders:

Start with $G = \{f_1, \ldots, f_s\}$.
For each pair $(g_i, g_j)$ not yet processed, compute $r = \overline{S(g_i, g_j)}^G$ (remainder upon division by $G$).
If $r \neq 0$, add $r$ to $G$ and process all new pairs involving $r$.
Repeat until no new nonzero remainders arise.

Termination follows from the ascending chain condition on monomial ideals (Dickson’s lemma): the sequence of leading term ideals is strictly increasing at each step where we add a new polynomial, but there are no infinite strictly ascending chains in $\mathbb{Z}_{\geq 0}^n$ under divisibility.

The algorithm produces a reduced Gröbner basis if we additionally normalise: make each element monic and reduce each element modulo the others. The reduced Gröbner basis is unique for a given ideal and ordering.

Example (Gröbner basis for a system): Consider the ideal $I = \langle x^2 + y - 1, \; x + y^2 - 1 \rangle$ in $\mathbb{Q}[x,y]$ with lex order $x \succ y$. Running Buchberger, the S-polynomial of the two generators reduces to a polynomial in $y$ alone (the elimination polynomial): $y^4 - y^3 - y^2 + 1 = (y-1)^2(y+1)(y-1)$, which factors as $(y-1)^3(y+1)$. Back-substituting recovers the solutions $(x,y) \in \{(0,1),(1,0),(0,-1)\}$ (and a repeated solution). This illustrates how lex Gröbner bases perform variable elimination.

Chapter 10: Applications

The algorithms developed in previous chapters — polynomial arithmetic, GCDs, CRT, linear algebra, factoring, and Gröbner bases — combine to address fundamental problems in symbolic mathematics. In this final chapter, we sketch several important application areas.

Symbolic Integration: The Risch Algorithm

The question “does a given elementary function have an elementary antiderivative?” was resolved algorithmically by Robert Risch in 1969. The Risch algorithm is a decision procedure — it always terminates and either produces an elementary antiderivative or proves none exists.

An elementary function is built from constants, $x$, by field operations, and the application of $\exp$, $\log$, and algebraic functions. The Risch algorithm works in a differential field extension tower.

The key subroutine for the rational function case uses partial fractions and resultants. For $f = p/q \in k(x)$ (with $p, q \in k[x]$, $\gcd(p,q) = 1$, $\deg(p) < \deg(q)$):

Theorem (Rothstein–Trager method): The integral $\int p/q \; dx$ is elementary if and only if all roots of the resultant $\text{Res}_x(q, p - t q') = 0$ (as a polynomial in $t$) are rational. If so, the integral is a sum of logarithms $\sum_{i} c_i \log(v_i(x))$ where $c_i$ are the roots and $v_i = \gcd(q, p - c_i q')$.

The computation requires exact GCDs (Chapter 6) and resultants — both operations we have studied. The logarithmic case already illustrates why symbolic integration is inherently an algebra problem.

Solving Polynomial Systems

A system of polynomial equations $f_1 = \cdots = f_s = 0$ defines an algebraic variety $V(I)$ in affine space. Solving the system means describing $V(I)$.

The elimination approach via Gröbner bases: compute a Gröbner basis of $\langle f_1, \ldots, f_s \rangle$ in lex order with $x_1 \succ x_2 \succ \cdots \succ x_n$. By the elimination theorem, the basis elements involving only $x_k, \ldots, x_n$ generate the $k$th elimination ideal $I \cap k[x_k, \ldots, x_n]$. In particular, the basis elements involving only $x_n$ form a univariate polynomial system, which can be solved by factoring or numerical methods. Back-substitution then recovers all solutions.

The resultant provides an alternative: to eliminate $x$ from a pair of equations $f(x,y) = 0$ and $g(x,y) = 0$, compute $R(y) = \text{Res}_x(f, g) \in k[y]$. The roots of $R$ are exactly the $y$-coordinates of the common zeros of $f$ and $g$.

Hilbert’s Nullstellensatz provides the theoretical bridge between algebra and geometry:

Theorem (Hilbert's Nullstellensatz): Let $k$ be algebraically closed, and let $I \subseteq k[x_1, \ldots, x_n]$ be an ideal. Then:

Weak form: $I$ has no common zero (i.e., $V(I) = \emptyset$) if and only if $1 \in I$.
Strong form: A polynomial $f$ vanishes on $V(I)$ if and only if $f^m \in I$ for some $m \geq 1$.

Both forms are decidable via Gröbner bases: the ideal membership test checks whether $1 \in I$ (no solutions) or whether $f^m \in I$ for large enough $m$.

The Role of Modular Methods in Applications

In practice, all the application algorithms are accelerated by the modular paradigm. For example, computing a Gröbner basis over $\mathbb{Q}$ is often done by computing Gröbner bases over several finite fields (cheaper, no coefficient growth) and then lifting via CRT and rational reconstruction. This modular Gröbner basis technique can be substantially faster than working over $\mathbb{Q}$ directly.

Similarly, symbolic integration over $\mathbb{Q}(x)$ can be accelerated by computing resultants modulo primes. The universal applicability of the modular paradigm — reduce, compute, lift — is one of the deepest themes of this course.

Complexity Summary

The following table summarises the asymptotic complexities of the main problems studied, where $n$ is the degree (or matrix size), $d$ is the number of variables, and $M(n)$ is the cost of polynomial multiplication:

Problem	Algorithm	Complexity
Polynomial multiplication	FFT (NTT)	$O(n \log n)$
Polynomial GCD	Modular Euclidean	$O(M(n) \log n)$
Polynomial evaluation (multi)	Subproduct tree	$O(M(n) \log n)$
Polynomial factoring over $\mathbb{F}_q$	Cantor–Zassenhaus	$O(n^2)$ expected
Polynomial factoring over $\mathbb{Z}$	LLL-based	$O(n^{5+\varepsilon})$
Integer determinant	CRT + Hadamard	$O(n^4 \log\\|A\\|)$
Rational linear system	Dixon $p$-adic	$O(n^4 \log\\|A\\|)$
Gröbner basis (2 variables)	Buchberger	$O(D^2)$, $D$ = regularity

The complexity of Gröbner basis computation in general is doubly exponential in the number of variables in the worst case, but polynomial for fixed number of variables and degree.

Problem	Algorithm	Complexity
Polynomial multiplication	FFT (NTT)	\(O(n \log n)\)
Polynomial GCD	Modular Euclidean	\(O(M(n) \log n)\)
Polynomial evaluation (multi)	Subproduct tree	\(O(M(n) \log n)\)
Polynomial factoring over \(\mathbb{F}_q\)	Cantor–Zassenhaus	\(O(n^2)\) expected
Polynomial factoring over \(\mathbb{Z}\)	LLL-based	\(O(n^{5+\varepsilon})\)
Integer determinant	CRT + Hadamard	\(O(n^4 \log\\|A\\|)\)
Rational linear system	Dixon \(p\)-adic	\(O(n^4 \log\\|A\\|)\)
Gröbner basis (2 variables)	Buchberger	\(O(D^2)\), \(D\) = regularity