Module factor_zassenhaus 

Univariate factorization over ℤ via Berlekamp–Zassenhaus. Univariate factorization over ℤ via Berlekamp–Zassenhaus (mod-p factoring, Hensel lifting, recombination).

This module implements the classical Zassenhaus algorithm for factoring a square-free primitive polynomial f ∈ ℤ[x] into irreducibles:

1. Choose primes. Small odd primes p with p ∤ lc(f) and f mod p square-free are tried; the one producing the fewest modular factors is kept. The sets of achievable factor degrees are intersected across all tried primes, which often proves irreducibility outright.
2. Factor mod p with Cantor–Zassenhaus (distinct-degree splitting followed by equal-degree splitting). Arithmetic in GF(p)[x] uses u64 coefficients with p < 2³¹.
3. Hensel lift the modular factorization to p^k where p^k > 2 · 2ⁿ · ‖f‖₂ · |lc(f)| (the Mignotte bound) using linear multifactor lifting.
4. Recombine by trying subsets of the lifted factors of increasing size. Each candidate is lc · ∏ gᵢ reduced to symmetric residues, made primitive, and tested by exact trial division. Cheap filters (achievable degree, constant-term divisibility) reject almost all spurious subsets without a division.
5. Verify the final factorization by multiplying back. If anything is inconsistent the input is returned unfactored — the result is never wrong, at worst incomplete.

The subset search is exponential in the number of modular factors, so it is bounded by MAX_RECOMBINATION_SUBSETS. When the budget is exhausted the remaining (possibly reducible) cofactor is returned as a single factor and a tracing::warn! is emitted. Callers inside the crate that need to know whether every returned factor is certified irreducible use factor_zassenhaus_checked, which reports that as a flag; the public functions keep their signatures.

Examples

use symplex::factor_zassenhaus::{factor_zassenhaus, Poly};
use num_bigint::BigInt;
use num_rational::Ratio;

let c = |n: i64| Ratio::from_integer(BigInt::from(n));
// x^4 + 4 = (x^2 - 2x + 2)(x^2 + 2x + 2)   (Sophie Germain identity)
let f = Poly::from_coeffs(vec![c(4), c(0), c(0), c(0), c(1)]);
let factors = factor_zassenhaus(&f);
assert_eq!(factors.len(), 2);
assert!(factors.iter().all(|(g, m)| g.degree() == Some(2) && *m == 1));

Modules

traits

Coefficient-ring traits used by GenPoly (re-exported so that the polynomial types above are fully documented and usable generically).

Structs

GenPoly

A dense univariate polynomial with coefficients in C.

Constants

MAX_KRONECKER_SUBSTITUTION_DEGREE

Largest univariate degree the Kronecker substitution in factor_multivariate is allowed to produce.

MAX_PRIME

Largest prime allowed for the u64 finite-field arithmetic (products of two residues must fit in u64). factor_mod_p accepts odd primes strictly below this bound.

MAX_RECOMBINATION_SUBSETS

Upper bound on the number of factor subsets examined during recombination. Beyond this the remaining cofactor is returned as-is.

PRIMES_TO_TRY

Number of usable primes whose modular factorizations are compared; the one with the fewest factors is used for lifting.

Functions

factor_mod_p

Factor a polynomial over the prime field GF(p).

factor_multivariate

Factor a multivariate polynomial over ℤ by Kronecker substitution.

factor_squarefree_z

Factor a square-free primitive polynomial f ∈ ℤ[x] (coefficients in ascending degree order) into irreducible integer factors.

factor_zassenhaus

Factor a polynomial over ℤ into primitive irreducible factors with multiplicities.

factor_zassenhaus_with_content

Factor a polynomial over ℤ, returning (content, factors).

is_irreducible_z

Decide whether a non-constant polynomial with rational coefficients is irreducible over ℚ.

Type Aliases

ModPFactorization

A factorization over GF(p): the leading coefficient and the monic irreducible factors (ascending coefficients in [0, p)) with multiplicities. Returned by factor_mod_p.

MultiFactorization

A factorization over ℤ of a multivariate polynomial: rational content and (factor, multiplicity) pairs. Returned by factor_multivariate.

Poly

A dense univariate polynomial over ℚ.