Multivariate factorization and sparse gcd¶
For the array workflow, see exact algebra.
Coefficient-array users can select this sparse GCD algorithm with
sparse.gcd(a, b, method="modular"), or retain its evidence through
sparse.gcd_checked. See exact array choices.
factor_multivariate and factor_multivariate_integer first extract common
variable powers and retain their multiplicities, then separate recursive
polynomial content, remove repeated factors, and use a monic transformation
followed by deterministic evaluation and exact multivariate Hensel lifting.
Repeated specializations are rejected. Three distinct deterministic good
points are compared by factor count and coefficient height. Split specialized
factors are lifted as formal series through the input's total parameter degree
and recombined by exact trial division. Rational factors are normalized
by their last stored coefficient; integer factors are primitive with positive
last stored coefficient. Results are sorted by total degree and stored
monomial/coefficient order. Multiplicities and the scalar reconstruct the
original input, including zero and constants.
factor_multivariate_gaussian and factor_multivariate_finite_field cover
QQi and prime fields, including repeated factors. They separate squarefree blocks before a mixed-radix
Kronecker substitution, univariate factorization and exact sparse trial
division. The dense image requires up to \(\prod_j (\deg_{x_j} f + 1)\)
coefficient slots per block \(f\), and subset recombination can take exponential work.
The shared budget covers image storage, candidate products and divisibility
tests. These routines preserve the input's monomial order and normalize every
factor to leading coefficient one. For KERNEL storage order, the scalar
accounts for normalization of each factor; it need not equal the input's last
stored coefficient.
squarefree_multivariate groups factors by multiplicity directly in sparse
storage. It supports QQ, QQi and prime fields; the array API promotes
integer input to QQ. SparseSquarefreeDecomposition stores the normalizing
scalar and monic blocks in increasing multiplicity. Its checker verifies the
product equation, without separately certifying squarefreeness or coprimality.
check_multivariate_factorization verifies the complete product. Like the
existing univariate product checker, it does not prove irreducibility.
sparse_gcd and sparse_gcd_integer use a fixed prime sequence, modular support
discovery, support-based interpolation and CRT reconstruction. Interpolation
solves for projective coefficients using evaluated univariate gcds; it does
not allocate a dense parameter-degree box. Failed interpolation or changing
support triggers recursive evaluation and Newton interpolation to discover
support again. Discovered monomial supports are reused across recursive samples
and primes through finite-field sparse linear interpolation; stale or singular
supports fall back to the accumulated Newton interpolant. Univariate content
and leading coefficients fix sample scaling;
degree drops discard unlucky samples. Exact trial division verifies
reconstruction. Polynomial content groups only occurring exponents and invokes
the same sparse gcd on fewer variables. Neither multivariate content nor modular
support discovery invokes PRS. Coprimality certification first tries a compact
modular affine projection over ZZ and QQ, with the exact resultant proof as a
fallback.
The returned GcdResult carries divisibility and independently checked
coprimality certificates. Both nonzero results include maximality evidence; the zero/zero
case has zero gcd and zero cofactors. This is an explicit sparse algorithm
entry point, independent of the existing gcd dispatch policy.
Integer and rational univariate factorization also include fresh exact LLL and van Hoeij trace-knapsack recombination. This private algorithm follows van Hoeij's 2002 knapsack method. It retains deterministic factor sorting and the existing product certificate interface. Hensel factors, their modulus and complementary inverses persist between precision increases, including the handoff from singleton peeling to the lattice.
MultivariateFactorization¶
@fieldwise_init
struct MultivariateFactorization[C: CoefficientRing](Copyable, Movable, Writable)
A sparse factorization whose product is independently checkable.
Parameters.
C: The coefficient ring.
Defined in src/polynomials/multivariate_factor.mojo.
| Field | Type | |
|---|---|---|
unit |
Self.C |
The scalar unit or content, including zero for zero input. |
factors |
List[Tuple[SparsePoly[Self.C], Int]] |
Distinct normalized irreducible factors with positive multiplicities. |
check_multivariate_factorization¶
def check_multivariate_factorization[C: CoefficientRing](f: SparsePoly[C], certificate: MultivariateFactorization[C], mut budget: Budget) raises PolyError -> Bool
Verify the sparse factor product without asserting irreducibility.
Parameters.
C: The coefficient ring.
Arguments.
f: The original polynomial.certificate: The scalar, sparse factors and multiplicities.budget: The shared work allowance.
Returns. Whether the factors with positive multiplicities multiply to the input.
Raises.
PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/multivariate_factor.mojo.
factor_multivariate¶
def factor_multivariate(f: SparsePoly[QQ], mut budget: Budget) raises PolyError -> MultivariateFactorization[QQ]
Factor a rational multivariate polynomial by monic transformation and lifting.
Arguments.
f: The input polynomial in any stored order, including zero and constants.budget: The shared work allowance.
Returns. The scalar and distinct monic irreducible factors with multiplicities, sorted deterministically.
Raises.
PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/multivariate_factor.mojo.
factor_multivariate_integer¶
def factor_multivariate_integer(f: SparsePoly[ZZ], mut budget: Budget) raises PolyError -> MultivariateFactorization[ZZ]
Factor an integer multivariate polynomial into primitive irreducible factors.
Arguments.
f: The input polynomial, including zero and constants.budget: The shared work allowance.
Returns. The integer content and primitive factors with positive leading coefficients and multiplicities.
Raises.
PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/multivariate_factor.mojo.
sparse_gcd¶
def sparse_gcd(f: SparsePoly[QQ], g: SparsePoly[QQ], mut budget: Budget) raises PolyError -> GcdResult[QQ]
Compute a monic rational gcd by sparse modular reconstruction.
Arguments.
f: The first sparse rational polynomial.g: The second polynomial in the same stored order.budget: The shared work allowance.
Returns. The monic gcd with cofactors and independently checkable maximality evidence.
Raises.
PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/sparse_gcd.mojo.
sparse_gcd_integer¶
def sparse_gcd_integer(f: SparsePoly[ZZ], g: SparsePoly[ZZ], mut budget: Budget) raises PolyError -> GcdResult[ZZ]
Compute an integer gcd using modular support discovery and sparse interpolation.
Arguments.
f: The first sparse integer polynomial.g: The second polynomial in the same stored order.budget: The shared work allowance.
Returns. The normalized gcd, cofactors, and explicit coprimality evidence when nonzero.
Raises.
PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/sparse_gcd.mojo.
factor_multivariate_gaussian¶
def factor_multivariate_gaussian(f: SparsePoly[QQi], mut budget: Budget) raises PolyError -> MultivariateFactorization[QQi]
Factor a sparse Gaussian-rational polynomial by exact recombination.
Arguments.
f: The polynomial in any order, including zero and constants.budget: The shared allowance, including the dense substitution image.
Returns. A scalar and distinct monic irreducibles with positive multiplicities, sorted by total degree, monomials and real-then-imaginary coefficients.
Raises.
PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/field_multivariate_factor.mojo.
factor_multivariate_finite_field¶
def factor_multivariate_finite_field(f: SparsePoly[ModInt], mut budget: Budget, seed: UInt64 = 0) raises PolyError -> MultivariateFactorization[ModInt]
Factor any sparse prime-field polynomial, including inseparable inputs.
Arguments.
f: The polynomial in any order, including zero and constants.budget: The shared allowance, including the dense substitution image.seed: The deterministic univariate splitting seed; defaults to zero.
Returns. A scalar and distinct monic irreducibles with positive multiplicities, sorted by total degree, monomials and residue coefficients.
Raises.
PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/field_multivariate_factor.mojo.
SparseSquarefreeDecomposition¶
@fieldwise_init
struct SparseSquarefreeDecomposition[C: CoefficientRing](Copyable, Movable, Writable)
A sparse polynomial's scalar and monic multiplicity blocks.
Parameters.
C: The coefficient ring.
Defined in src/polynomials/sparse_squarefree.mojo.
| Field | Type | |
|---|---|---|
unit |
Self.C |
The normalizing scalar, or zero for zero input. |
factors |
List[Tuple[SparsePoly[Self.C], Int]] |
Nonconstant blocks in increasing multiplicity, preserving the input order. |
squarefree_multivariate¶
def squarefree_multivariate[C: CoefficientField](f: SparsePoly[C], mut budget: Budget) raises PolyError -> SparseSquarefreeDecomposition[C]
Group sparse factors by multiplicity without factoring into irreducibles.
Parameters.
C: A characteristic-zero field or ModInt prime field.
Arguments.
f: The polynomial in any stored order, including zero and constants.budget: The shared work allowance.
Returns. The normalizing scalar and monic, pairwise coprime squarefree blocks.
Raises.
PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/sparse_squarefree.mojo.
check_sparse_squarefree_product¶
def check_sparse_squarefree_product[C: CoefficientRing](f: SparsePoly[C], decomposition: SparseSquarefreeDecomposition[C], mut budget: Budget) raises PolyError -> Bool
Check a sparse multiplicity product without asserting squarefreeness.
Parameters.
C: The coefficient ring.
Arguments.
f: The original polynomial.decomposition: The proposed scalar, blocks and multiplicities.budget: The shared work allowance.
Returns. Whether all multiplicities are positive and the product equals f.
Raises.
PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/sparse_squarefree.mojo.