Algebraic Number Fields & Galois Theory

Algebraic number fields are the central structures of computer algebra connecting polynomial algebra with number theory. In oCAS, an algebraic number field $\mathbb{Q}(\alpha)$ is not only a coefficient field — allowing polynomial arithmetic and factorization over the extension field — but also a unified abstraction for Galois fields $\mathrm{GF}(p^d)$. This chapter starts from the basic concepts of minimal polynomials and field extensions, systematically presents the arithmetic on algebraic number fields, norm algorithms, and modular methods, and shows how these theories map onto the oCAS implementation.

Prerequisites

Before reading this chapter, we recommend studying:

• Polynomial Algebra — polynomial rings, degree, division with remainder, irreducibility
• Finite Fields & Modular Arithmetic — construction of $\mathbb{F}_p$, modular inverses, CRT
• Linear Algebra — matrix operations, determinants, resultants
• Polynomial GCD & Factorization — square-free factorization, Hensel lifting, modular GCD

Minimal Polynomials

Let $K$ be an extension field of $\mathbb{Q}$ and $\alpha \in K$. If there exists a non-zero polynomial $f \in \mathbb{Q}[x]$ with $f(\alpha) = 0$, then $\alpha$ is called an algebraic element. The monic polynomial $m(x)$ of lowest degree satisfying this condition is called the minimal polynomial of $\alpha$.

Properties:

1. The minimal polynomial is irreducible in $\mathbb{Q}[x]$.
2. Every polynomial $f$ with $f(\alpha) = 0$ satisfies $m \mid f$.
3. The minimal polynomial is unique up to isomorphism.

Example: the minimal polynomial of $\sqrt{2}$ is $x^2 - 2$, since $(\sqrt{2})^2 - 2 = 0$ and $x^2 - 2$ is irreducible over $\mathbb{Q}$ (Eisenstein's criterion, $p = 2$).

Field Extensions and Extension Degree

Given fields $F \subseteq K$, one calls $K$ a field extension of $F$, written $K/F$. The dimension of $K$ as an $F$-vector space is called the extension degree:

$$[K : F] = \dim_F K$$

When $K = F(\alpha)$ (generated by a single algebraic element), it is called a simple extension. The key theorem:

$$[F(\alpha) : F] = \deg(m_\alpha)$$

where $m_\alpha$ is the minimal polynomial of $\alpha$ over $F$. Hence ${1, \alpha, \alpha^2, \ldots, \alpha^{d-1}}$ ($d = [K:F]$) is a basis of $K$ as an $F$-vector space.

Field Towers and the Tower Law

For a tower of fields $F \subseteq K \subseteq L$, the extension degrees satisfy the tower law:

$$[L : F] = [L : K] \cdot [K : F]$$

Example: let $\alpha = \sqrt[3]{2}$ and $\omega = e^{2\pi i/3}$. Then $\mathbb{Q}(\alpha, \omega) / \mathbb{Q}(\alpha)$ has degree 2 ($\omega$ satisfies $x^2 + x + 1$), $\mathbb{Q}(\alpha) / \mathbb{Q}$ has degree 3, and therefore $[\mathbb{Q}(\alpha, \omega) : \mathbb{Q}] = 6$.

Basic Concepts

Representation of Elements of $\mathbb{Q}(\alpha)$

Let $m(x) = x^d + a_{d-1}x^{d-1} + \cdots + a_0$ be the minimal polynomial of $\alpha$, with $d = [K:\mathbb{Q}]$. From $m(\alpha) = 0$ we obtain

$$\alpha^d = -(a_{d-1}\alpha^{d-1} + \cdots + a_0)$$

so every element of $\mathbb{Q}(\alpha)$ can be represented uniquely as

$$c_0 + c_1 \alpha + c_2 \alpha^2 + \cdots + c_{d-1} \alpha^{d-1}, \quad c_i \in \mathbb{Q}$$

i.e. as a polynomial in $\alpha$ of degree $< d$. This representation is unique, because the difference of two distinct polynomials of degree $< d$ would be a non-zero multiple of $m(x)$ (a polynomial of degree $< d$ cannot be a multiple of $m$ unless it is zero).

Addition and scalar multiplication operate term by term on the coefficients. Multiplication first multiplies the polynomials (obtaining a polynomial of degree $\le 2(d-1)$) and then reduces modulo $m(\alpha)$ — repeatedly replacing $\alpha^d$ by $-\sum_{i=0}^{d-1} a_i \alpha^i$ until the degree is $< d$.

Example: $\mathbb{Q}(\sqrt{2})$ with $m(x) = x^2 - 2$. Elements are $a + b\sqrt{2}$ ($a, b \in \mathbb{Q}$). Multiplication:

$$(1 + \sqrt{2})(3 - \sqrt{2}) = 3 + 3\sqrt{2} - \sqrt{2} - 2 = 1 + 2\sqrt{2}$$

Computing Inverses

An element $a(\alpha) \in \mathbb{Q}(\alpha)$ is invertible if and only if $a(\alpha) \ne 0$. The key tool for computing inverses is the extended Euclidean algorithm: applying it to $a(x)$ and $m(x)$ in $\mathbb{Q}[x]$ gives

$$s(x) \cdot a(x) + t(x) \cdot m(x) = g(x)$$

where $g = \gcd(a, m)$. Since $m$ is irreducible and $a \not\equiv 0 \pmod{m}$, we must have $\deg(g) = 0$, i.e. $g$ is a non-zero constant. After normalizing $g = 1$, we get

$$a(\alpha)^{-1} = s(\alpha) \bmod m(\alpha)$$

Example: compute $(1 + \sqrt{2})^{-1}$ in $\mathbb{Q}(\sqrt{2})$.

Use the extended Euclidean algorithm to find $s(x)(1+x) + t(x)(x^2-2) = 1$:

• $x^2 - 2 = (x - 1)(1 + x) + (-1)$
• hence $(-1) = (x^2 - 2) - (x-1)(1+x)$
• normalizing: $1 = (x-1)(1+x) - (x^2-2)$

So $s(x) = x - 1$; verification: $(1+\sqrt{2})(\sqrt{2}-1) = \sqrt{2}^2 - 1 = 1$. ✓

Core Theory

Construction of $\mathrm{GF}(p^d)$

The mod-$p$ "projection" of an algebraic number field needs the finite field $\mathrm{GF}(p^d)$. The construction is completely parallel to that of $\mathbb{Q}(\alpha)$:

1. Take an irreducible polynomial $\bar{m}(x)$ of degree $d$ in $\mathbb{F}_p[x]$ (usually the image of the minimal polynomial $m(x)$ modulo $p$).
2. $\mathrm{GF}(p^d) = \mathbb{F}_p[x]/(\bar{m}(x))$.
3. Elements are $c_0 + c_1\alpha + \cdots + c_{d-1}\alpha^{d-1}$ with $c_i \in \mathbb{F}_p$.
4. The operations are the same as for $\mathbb{Q}(\alpha)$, except that coefficients are reduced modulo $\mathbb{F}_p$.

Key condition: $m(x) \bmod p$ must still be an irreducible polynomial of degree $d$. If $p$ divides a denominator of $m$ or makes $m \bmod p$ degenerate (lower degree or reducible), this prime cannot be used for modular methods.

Example: $m(x) = x^2 + 1$ (the minimal polynomial of $\mathbb{Q}(i)$). Over $\mathbb{F}_3$, $x^2 + 1$ is irreducible (since $0^2+1=1$, $1^2+1=2$, $2^2+1=2$ are all non-zero), so $\mathrm{GF}(3^2) = \mathbb{F}_3[x]/(x^2+1)$, whose multiplicative group has order 8.

Trager's Norm Algorithm

Let $K = \mathbb{Q}(\alpha)$ and let $f \in K[x]$ be square-free. Trager's algorithm solves the factorization problem by "reducing" it from $K[x]$ to $\mathbb{Q}[x]$. The core tool is the norm map.

Definition of the Norm

For $f \in K[x]$, its norm $N(f) \in \mathbb{Q}[x]$ is defined as:

$$N(f)(x) = \operatorname{Res}_\alpha\bigl(m(\alpha),, f(x, \alpha)\bigr)$$

i.e. viewing $f(x, \alpha)$ as a polynomial in $\alpha$ (with coefficients in $\mathbb{Q}[x]$), take its resultant with $m(\alpha)$ (eliminating $\alpha$).

Key property: if $f$ is irreducible in $K[x]$, then $N(f)$ is a power of an irreducible polynomial in $\mathbb{Q}[x]$. More precisely, if $f = g_1 g_2 \cdots g_r$ is the irreducible factorization in $K[x]$, then

$$N(f) = N(g_1) \cdot N(g_2) \cdots N(g_r)$$

and each $N(g_i)$ is irreducible in $\mathbb{Q}[x]$.

Computing the Norm by Evaluation–Interpolation

Computing the resultant $\operatorname{Res}_\alpha(m, f(x,\alpha))$ directly is expensive for high-degree polynomials. oCAS uses the evaluation–interpolation method:

1. The norm $N(f)$, as a polynomial in $x$, has degree $\deg_x(f) \cdot [K:\mathbb{Q}]$.
2. Take $n = \deg_x(f) \cdot d + 1$ rational points $x_0, x_1, \ldots, x_{n-1}$ (using the symmetric sequence $0, -1, 1, -2, 2, \ldots$ to keep the arithmetic small).
3. At each $x_j$, compute $f(x_j, \alpha) \in K$ (Horner evaluation), then compute the scalar resultant $\operatorname{Res}_\alpha(m, f(x_j, \alpha))$.
4. Recover $N(f)$ by Newton divided-difference interpolation.

This is exact (rational arithmetic without rounding) and avoids the direct computation of a high-degree resultant.

The Trager Shift

Even if $f$ is square-free, its norm $N(f)$ may have square factors (e.g. the norm of $f = x - \alpha$ over $\mathbb{Q}(\sqrt{2})$ is $x^2 - 2$, already square-free; but the norm of $f = x^2 - 2$ is $(x^2-2)^2$, which has squares).

Trager shift: apply the substitution $x \mapsto x - s\alpha$ to $f(x)$ ($s \ge 0$), obtaining $g(x) = f(x - s\alpha)$. Since only finitely many $s$ are "bad" (make $N(g)$ non-square-free), an $s$ with square-free $N(g)$ always exists.

Algorithm:

for s = 0, 1, 2, ...:
    g(x) ← f(x − s·α)          // Horner composition
    R(x) ← N(g)(x)              // evaluation–interpolation norm
    if R(x) is square-free (verified modulo primes):
        return (s, g, R)

oCAS tries at most MAX_TRAGER_SHIFTS = 100 shift values. Square-freeness is verified by a modular method: for several primes $p$, if $R \bmod p$ is square-free in $\mathbb{F}_p[x]$, then $R$ is square-free in $\mathbb{Q}[x]$ (a sufficient but not necessary condition — which is exactly the "acceptance" criterion we need).

The Factorization Flow

Given a square-free $f \in K[x]$:

1. Find a shift: $(s, g, R) \leftarrow \text{norm_with_shift}(f)$.
2. Factor the norm: $R = r_1 \cdot r_2 \cdots r_k$ (irreducible factorization in $\mathbb{Q}[x]$).
3. Pull back to $K$: for each $r_i$, compute $\gcd_K(g, r_i)$ (embedding $r_i$ into $K[x]$) to obtain the factors of $f$ in $K[x]$.
4. Undo the shift: $x \mapsto x + s\alpha$ to restore the original variable.

Correctness guarantee: the factors $r_i$ of the norm correspond to factors of $g$, and the GCD in $K[x]$ extracts these factors exactly.

Modular GCD over Number Fields (Encarnación's Method)

The $\gcd_K$ in step 3 (the GCD of two polynomials in $K[x]$) is the computational bottleneck. Doing the Euclidean GCD directly in $K[x]$ causes severe coefficient growth (the coefficients are elements of $\mathbb{Q}(\alpha)$, i.e. $\alpha$-polynomials over the rationals).

The modular method (Encarnación) projects the problem onto $\mathrm{GF}(p^d)$:

Input: a, b ∈ K[x] (K = ℚ(α))
Output: monic gcd(a, b) ∈ K[x]

1. CRT state: residues = None, modulus = 1
2. for p in primes_from(2):
3.     if m(x) mod p is reducible or loses degree: skip  // m degenerates over F_p; this prime is unusable
4.     GF ← GF(p^d) = F_p[x]/(m mod p)
5.     if p | lc(a) or p | lc(b): skip
6.     g_p ← monic(gcd(a mod GF, b mod GF))   // GCD over GF(p^d)[x]
7.     if deg(g_p) > best_deg: skip            // unlucky prime
8.     if deg(g_p) < best_deg:
9.         best_deg ← deg(g_p)
10.        residues ← coefficient table of g_p  // [x-degree][α-degree] F_p values
11.        modulus ← p
12.    else:
13.        residues ← CRT(residues, g_p)  // merge coefficient by coefficient
14.        modulus ← modulus × p
15.
16.    // rational reconstruction + trial division verification
17.    candidate ← rational_reconstruct(residues, modulus)
18.    if candidate | a and candidate | b:
19.        return candidate
20.
21. return dense_euclidean_gcd(a, b)  // safe fallback

Prime Selection

Not every prime is suitable for the modular method. The requirements are:

1. $m(x) \bmod p$ stays irreducible with the same degree: otherwise $\mathbb{F}_p[\alpha]/(m) \ne \mathrm{GF}(p^d)$ and the GCD semantics are wrong.
2. $p$ does not divide the leading coefficients: otherwise the mapped polynomials drop in degree.
3. $p$ does not divide any coefficient denominator: the map from the rationals to $\mathbb{F}_p$ would fail.

Detecting Unlucky Primes

If the modular GCD over a prime $p$ has degree higher than the current best, the prime is "unlucky" — $p$ divides a coefficient of some proper factor. The result is simply discarded.

If the modular GCD degree is lower than the current best, all previous primes were unlucky; discard the accumulated state and restart with the new result.

Rational Reconstruction

The residues after CRT combination are large integers (modulo a large composite). For each coefficient (each component of the $\alpha$-polynomial), rational reconstruction recovers a rational number from the integer pair:

Given an integer $a$ and a modulus $m$, find a rational number $n/d$ such that $a \equiv n/d \pmod{m}$ with $|n|, |d| \le \sqrt{m/2}$.

The Wang/extended-Euclid method tracks the sequence $(r_i, t_i)$ until $|r_1|, |t_1| \le \sqrt{m/2}$, verifying that $a \cdot d \equiv n \pmod{m}$.

Trial Division Verification

The candidate GCD from rational reconstruction must be verified by trial division: check that it divides both original inputs $a$ and $b$. Only verified results are returned.

oCAS tries at most MAX_ANF_GCD_PRIMES = 1000 primes. In practice more than a few dozen are rarely needed. In the worst case it falls back to the dense Euclidean GCD over $K[x] = \mathbb{Q}(\alpha)[x]$ (slow but guaranteed correct).

Cyclotomic Fields $\mathbb{Q}(\zeta_n)$

The number field $\mathbb{Q}(\zeta_n)$ generated by a primitive $n$-th root of unity $\zeta_n = e^{2\pi i/n}$ is called a cyclotomic field.

The Minimal Polynomial

The minimal polynomial of $\zeta_n$ is the cyclotomic polynomial:

$$\Phi_n(x) = \prod_{\substack{1 \le k \le n \ \gcd(k,n)=1}} \left(x - e^{2\pi i k/n}\right)$$

Its degree is $\varphi(n)$ (Euler's totient function). $\Phi_n$ is irreducible in $\mathbb{Q}[x]$.

Examples:

• $\Phi_1(x) = x - 1$
• $\Phi_2(x) = x + 1$
• $\Phi_3(x) = x^2 + x + 1$
• $\Phi_4(x) = x^2 + 1$
• $\Phi_6(x) = x^2 - x + 1$
• $\Phi_p(x) = x^{p-1} + x^{p-2} + \cdots + 1$ ($p$ prime)

The cyclotomic polynomials satisfy $x^n - 1 = \prod_{d \mid n} \Phi_d(x)$ and can be computed factor by factor using Möbius inversion.

Properties of the Field

• $[\mathbb{Q}(\zeta_n) : \mathbb{Q}] = \varphi(n)$.
• $\mathbb{Q}(\zeta_n)$ is an Abelian extension of $\mathbb{Q}$ (its Galois group is $(\mathbb{Z}/n\mathbb{Z})^*$).
• Its ring of integers is $\mathbb{Z}[\zeta_n]$; the discriminant depends on the prime factors of $n$.

Example: the extension degree of $\mathbb{Q}(\zeta_5)$ is $\varphi(5) = 4$, with minimal polynomial $\Phi_5(x) = x^4 + x^3 + x^2 + x + 1$. Elements are represented as $a_0 + a_1\zeta + a_2\zeta^2 + a_3\zeta^3$ ($a_i \in \mathbb{Q}$).

In oCAS, constructing a cyclotomic field only requires specifying the cyclotomic polynomial:

#![allow(unused)]
fn main() {
use ocas_domain::{AlgebraicNumberField, Domain, Rational, RationalDomain};

// Q(ζ_5): minimal polynomial x^4 + x^3 + x^2 + x + 1
// ascending powers: [1, 1, 1, 1, 1]
let field = AlgebraicNumberField::new(
    RationalDomain,
    vec![
        Rational::new(1, 1),
        Rational::new(1, 1),
        Rational::new(1, 1),
        Rational::new(1, 1),
        Rational::new(1, 1),
    ],
);
let zeta = field.alpha(); // ζ_5
// ζ_5^5 = 1 (guaranteed by the minimal polynomial)
let z5 = field.pow(&zeta, 5);
assert_eq!(z5, field.one());
}

Implementation in oCAS

Core Data Structures

The algebraic number field implementation lives in ocas-domain/src/algebraic.rs.

AlgebraicElement<E>

A field element — the residue class of the minimal polynomial, stored as a unique polynomial representative of degree $< d$:

#![allow(unused)]
fn main() {
pub struct AlgebraicElement<E> {
    coeffs: Vec<E>,  // ascending powers, trailing zeros trimmed
}
}

• The empty vector represents zero.
• PartialEq compares the coefficient vectors directly (semantic equality = structural equality, because the representative is unique).
• Display outputs from highest to lowest degree: (c_d)·α^d + … + (c_1)·α + c_0 (the constant term has no parentheses; e.g. 1 + 2α displays as (2)·α + 1).

#![allow(unused)]
fn main() {
// accessing the coefficients
let e = field.element(vec![r(1, 1), r(2, 1)]); // 1 + 2α
assert_eq!(e.coeffs(), &[r(1, 1), r(2, 1)]);
}

AlgebraicExtension<D>

The field extension $D[\alpha]/(m(\alpha))$:

#![allow(unused)]
fn main() {
pub struct AlgebraicExtension<D: Domain> {
    base: D,              // base field (RationalDomain or FiniteField)
    min_poly: Vec<D::Element>,  // minimal polynomial (ascending powers, monic)
}
}

Construction:

#![allow(unused)]
fn main() {
// Q(√2): m(x) = x² − 2, ascending powers [−2, 0, 1]
let field = AlgebraicNumberField::new(
    RationalDomain,
    vec![Rational::new(-2, 1), Rational::new(0, 1), Rational::new(1, 1)],
);
}

Invariants (checked by debug_assert):

• The minimal polynomial has degree $\ge 1$ (at least 2 coefficients).
• The minimal polynomial is monic (leading coefficient = 1).
• Irreducibility is not verified: a ring modulo a reducible modulus has zero divisors; inv returns None for non-units.

Key methods:

AlgebraicNumberField

A type alias:

#![allow(unused)]
fn main() {
pub type AlgebraicNumberField = AlgebraicExtension<RationalDomain>;
}

Arithmetic Operations

AlgebraicExtension<D> implements the Domain and EuclideanDomain traits.

Addition/subtraction: add/subtract the coefficient polynomials term by term.

Multiplication: multiply the polynomials, then reduce modulo the minimal polynomial (reduce). The reduction process:

while v.len() > d:
    c ← v.pop()                    // top coefficient
    offset ← v.len() − d
    for i in 0..d:
        v[offset + i] −= c · m[i] // subtract the expansion of c·α^d

This exploits the monicity of $m$ (leading coefficient = 1); no division is needed.

Inversion: the extended Euclidean algorithm. Compute $s(x) \cdot a(x) + t(x) \cdot m(x) = 1$ and return $s(\alpha) \bmod m(\alpha)$. If $\gcd(a, m) \ne 1$ ($a$ is a zero divisor), return None.

Division: div(a, b) = a * inv(b). Division fails when inv(b) is None.

EuclideanDomain: over a field, division with remainder degenerates to exact division (the remainder is always zero). GCD degenerates to: return zero if both are zero, otherwise return one.

Factorization over Number Fields (Trager's Algorithm)

The factorization implementation lives in ocas-poly/src/factor/algebraic.rs.

Overall Flow

Input: f ∈ K[x] (K = ℚ(α))
Output: [(g₁, e₁), (g₂, e₂), …] such that f = lc(f) · ∏ gᵢ^eᵢ

1. if all coefficients of f are ℚ-constants:
       // fast path: factor over ℚ first, then split each factor over K
       f_Q ← drop the α-components (then clear denominators and take the primitive part)
       for (h, e) in factor_primitive(f_Q):
           for g in factor_square_free_anf(K, embed(h)):
               output (g, e)
       return
2. for (g, e) in square_free_anf(K, f):      // Yun square-free factorization
3.     for h in factor_square_free_anf(K, g): // Trager factorization
4.         output (h, e)

Square-Free Factorization (square_free_anf)

Implements Yun's algorithm over $K[x]$, but uses gcd_anf (modular GCD) instead of the generic pseudo-remainder GCD. This is because the coefficients of elements of $\mathbb{Q}(\alpha)$ are rational numbers, and the coefficient growth of the pseudo-remainder GCD is even worse over arbitrary-precision rationals.

Trager Factorization (factor_square_free_anf)

#![allow(unused)]
fn main() {
fn factor_square_free_anf(field, f):
    if deg(f) <= 1:
        return [monic(f)]
    (s, g, R) ← norm_with_shift(field, f)  // find a shift making the norm square-free
    rational_factors ← factor_square_free_rationals(R)  // factor the norm over ℚ
    if len(rational_factors) <= 1:
        return [monic(f)]  // norm irreducible → f irreducible
    remaining ← g
    out ← []
    back_shift ← s·α  // inverse of the shift
    for r_i in rational_factors:
        r_i_K ← embed(r_i)  // embed into K[x]
        h ← gcd_anf(field, r_i_K, remaining)  // modular GCD
        remaining ← remaining / h
        out.append(monic(compose_linear(h, back_shift)))  // undo the shift
    return out
}

Modular GCD (gcd_anf)

A complete implementation of Encarnación's method. The CRT state tracks the $\alpha$-components of every coefficient:

#![allow(unused)]
fn main() {
// CRT state: residues[x-degree][α-degree] are integer residues
let mut residues: Option<Vec<Vec<Integer>>> = None;
let mut modulus = Integer::from(1);
}

Each iteration:

1. Take the next prime $p$ and check whether $m \bmod p$ is irreducible (min_poly_irreducible_mod: map the coefficients to $\mathbb{F}_p$ and verify the degree and irreducibility).
2. Construct $\mathrm{GF}(p^d) = \mathbb{F}_p[\alpha]/(m \bmod p)$.
3. Map $a, b$ to $\mathrm{GF}(p^d)[x]$ and compute the monic GCD.
4. Merge into the CRT state.
5. Try rational reconstruction + trial division verification.

Unlucky-prime handling: compare the modular GCD degree with the historical best. Higher → discard; lower → reset.

Fallback: after more than MAX_ANF_GCD_PRIMES = 1000 primes, use the dense Euclidean GCD in $K[x]$.

Mapping from $\mathbb{Q}$ to $\mathrm{GF}(p^d)$

Mapping a rational number to $\mathbb{F}_p$:

#![allow(unused)]
fn main() {
fn map_rational_fp(c: &Rational, fp: &FiniteField) -> Option<FiniteFieldElement> {
    let num = fp.element(c.numer().to_bigint());  // numerator mod p
    let den = fp.element(c.denom().to_bigint());  // denominator mod p
    fp.div(&num, &den)  // num · den^{-1} mod p; returns None if the denominator is zero
}
}

Mapping an element of $\mathbb{Q}(\alpha)$ to $\mathrm{GF}(p^d)$:

#![allow(unused)]
fn main() {
fn map_element_gf(e: &AlgebraicElement<Rational>, gf: &GaloisField) -> Option<...> {
    e.coeffs().iter().map(|c| map_rational_fp(c, gf.base_domain())).collect()
}
}

Mapping an $\alpha$-polynomial to $\mathrm{GF}(p^d)[x]$: map coefficient by coefficient.

Shifts and Composition

compose_linear(f, shift) computes $f(x + \text{shift})$ by Horner's method:

#![allow(unused)]
fn main() {
fn compose_linear<D: Domain>(f: &UP<D>, shift: &D::Element) -> UP<D> {
    let domain = f.domain().clone();
    // linear = x + shift
    let linear = UP::from_coeffs(domain.clone(), vec![shift.clone(), domain.one()]);
    let mut acc = UP::from_coeffs(domain.clone(), Vec::new()); // zero polynomial
    for c in f.coeffs().iter().rev() {
        // acc ← acc · (x + shift) + c (polynomial Horner composition)
        acc = acc
            .mul(&linear)
            .add(&UP::from_coeffs(domain.clone(), vec![c.clone()]));
    }
    acc
}
}

In Trager's algorithm, the shift is $x \mapsto x - s\alpha$ and the inverse shift is $x \mapsto x + s\alpha$.

Norm Computation

norm_eval_interp implements the evaluation–interpolation norm:

#![allow(unused)]
fn main() {
fn norm_eval_interp(field: &AlgebraicNumberField, g: &UP<AlgebraicNumberField>) -> UP<RationalDomain> {
    let deg_x = g.degree().unwrap_or(0);
    let d = field.extension_degree();
    let n_points = d * deg_x + 1;  // number of points needed for interpolation
    // symmetric points 0, −1, 1, −2, 2, ...
    for j in 0..n_points {
        let x = Rational::new(((j+1)/2) * sign, 1);
        // Horner evaluation g(x) ∈ K
        let val = horner_eval(g, field.from_base(x));
        // scalar resultant Res_α(m, val(α))
        let norm_val = m_poly.resultant(&val_as_poly);
        xs.push(x); ys.push(norm_val);
    }
    interpolate_rational(&xs, &ys)  // Newton divided-difference interpolation
}
}

The Unified Abstraction of Galois Fields

The generic design of AlgebraicExtension lets $\mathbb{Q}(\alpha)$ and $\mathrm{GF}(p^d)$ share the same code:

In gcd_anf, the GCD computation for the same prime $p$ is carried out in $\mathrm{GF}(p^d)[x]$, and the results are then combined back into $\mathbb{Q}(\alpha)[x]$ by CRT.

Advanced Topics

Reducible Moduli and Zero Divisors

When $m(x) \bmod p$ is reducible over $\mathbb{F}_p$, the ring $\mathbb{F}_p[x]/(m)$ is not a field — it has zero divisors. oCAS does not verify irreducibility of the minimal polynomial and allows constructing the ring modulo a reducible modulus. In that case:

• inv returns None for non-zero zero divisors (the extended Euclidean algorithm gives $\gcd \ne 1$).
• gcd_anf skips such primes (the min_poly_irreducible_mod check).

Example: $m(x) = x^2 - 1 = (x-1)(x+1)$ is reducible over $\mathbb{Q}$. The ring $\mathbb{Q}[x]/(x^2-1)$ has the zero divisor $\alpha - 1$ (since $(\alpha-1)(\alpha+1) = \alpha^2-1 = 0$).

#![allow(unused)]
fn main() {
let field = AlgebraicNumberField::new(
    RationalDomain,
    vec![Rational::new(-1, 1), Rational::new(0, 1), Rational::new(1, 1)],
);
let alpha = field.alpha();
let a = field.sub(&alpha, &field.one());
assert!(field.inv(&a).is_none()); // α − 1 is a zero divisor
}

Efficiency of Prime Selection for Modular GCD

In practice, most small primes satisfy the condition that $m \bmod p$ is irreducible. For a minimal polynomial of degree $d$, the probability that a random degree-$d$ polynomial over $\mathbb{F}_p$ is irreducible is about $1/d$ (by the formula counting irreducible polynomials). On average, roughly $d$ primes must be tried to find a usable one.

oCAS iterates over primes starting from $p = 2$ (using the primes_from iterator). For larger $d$ (e.g. $d \ge 6$), more primes may need to be skipped, but the budget of 1000 primes is almost always sufficient.

The Trade-off Between Coefficient Growth and Rational Reconstruction

The core advantage of the modular method is that it avoids coefficient growth: arithmetic over $\mathrm{GF}(p^d)$ is modular and the coefficients stay bounded. However, the residues after CRT combination grow as $O(\prod p_i)$, and rational reconstruction requires the bound $\sqrt{m/2}$.

In practice, if the coefficients of the true GCD are small (the typical case), 2–5 primes usually suffice. If the coefficients are large (e.g. a complicated GCD over a high-degree extension), more primes may be needed to accumulate enough CRT modulus.

Relation to Multivariate Factorization

Trager's norm algorithm can also be used for factoring multivariate polynomials over algebraic number fields (Wang EEZ + Zassenhaus recombination), but this is not yet implemented in oCAS. The current multivariate factorization (ocas-poly/src/factor/multivariate.rs) supports only $\mathbb{Z}$ and $\mathbb{F}_p$ coefficients.

Computational Complexity

For $f \in K[x]$ ($K = \mathbb{Q}(\alpha)$, $[K:\mathbb{Q}] = d$, $\deg f = n$):

The overall bottleneck is usually the resultant evaluation in the norm computation (for large $d$) or the prime selection for the modular GCD (when many unlucky primes occur).

References

• [Cohen] H. Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138, 1993. — Chapter 2 (representation and arithmetic of number fields), Chapter 3 (basic number-theoretic functions), Chapter 4 (ideals and class groups).
• [Trager] B. M. Trager, "Algebraic factoring and rational function integration", Proc. SYMSAC 1976, pp. 196–208. — The original paper on Trager's norm algorithm.
• [Encarnación] M. J. Encarnación, "Computing GCDs of polynomials over algebraic number fields", J. Symbolic Computation 20:3, 1995, pp. 299–313. — The modular GCD method over number fields.
• [Gathen–Gerhard] J. von zur Gathen & J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge, 2013. — Chapter 6 (field extensions), Chapters 14–15 (factorization).
• [Cox–Little–O'Shea] D. Cox, J. Little & D. O'Shea, Ideals, Varieties, and Algorithms, 4th ed., Springer UTM, 2015. — Chapter 4 (Gröbner bases over polynomial rings and elimination).
• [Lang] S. Lang, Algebra, 3rd ed., Springer GTM 211, 2002. — Chapter 5 (basic theory of field extensions).

See also: Coefficient Domains API — the complete API of AlgebraicExtension, AlgebraicNumberField, AlgebraicElement; Factorization API — using DenseUnivariatePolynomial::factor() over algebraic number fields; Polynomial GCD & Factorization — the general theory of modular GCD and Hensel lifting; Finite Fields & Modular Arithmetic — the construction of $\mathbb{F}_p$ and $\mathrm{GF}(p^d)$.