poly.mojo v1.0.2
Search /
Core API

Univariate factorization

These operations factor univariate polynomials over the rationals, integers, Gaussian rationals, and prime fields. All work uses the caller's shared budget. Returned factor lists are sorted by degree, then by coefficients from the leading one down.

algebra.mojo Download
"""Factorization, ideal membership, and certified real-root counts."""
from apn_mojo import Rational
from polynomials import Budget, QQ, NoContext, DensePoly, SparsePoly, MonomialOrder, factor, squarefree, check_factorization, check_squarefree_product, groebner, membership, check_membership, count_roots, check_root_count, isolate_real_roots


def main() raises:
    var work = Budget()
    var f = DensePoly[QQ].from_coefficients(0, NoContext(), [QQ(Rational(-1)), QQ.zero(NoContext()), QQ.one(NoContext())], work)
    var factors = factor(f, work)
    var blocks = squarefree(f, work)
    if not check_factorization(f, factors, work) or not check_squarefree_product(f, blocks, work):
        raise Error("factor product did not check")
    print("Factors:", len(factors.factors))

    var order = MonomialOrder(MonomialOrder.LEX, [0, 1], work)
    var x = SparsePoly[QQ].variable(0, order, NoContext(), work)
    var y = SparsePoly[QQ].variable(1, order, NoContext(), work)
    var one = SparsePoly[QQ].constant(QQ.one(NoContext()), order, work)
    var generators: List[SparsePoly[QQ]] = [x.sub(y, work), x.pow(2, work).sub(one, work)]
    var basis = groebner(generators, order, work)
    var member = y.pow(2, work).sub(one, work)
    var proof = membership(member, generators, order, work)
    if not proof or not check_membership(member, generators, proof.value(), work):
        raise Error("membership identity did not check")
    print("Basis elements:", len(basis.basis))

    var low = QQ(Rational(-2))
    var high = QQ(Rational(2))
    var counted = count_roots(f, low, high, work)
    var roots = isolate_real_roots(f, work)
    if counted.count != 2 or not check_root_count(f, counted, work):
        raise Error("root count did not check")
    print("Exact real roots:", len(roots.exact_roots))
    print("All certificates checked")

Run from the repository root pixi run mojo run -I build docs/examples/algebra.mojo

Output

Factors: 2
Basis elements: 2
Exact real roots: 2
All certificates checked

The polynomial \((x-1)^2(x+2)\) has two distinct rational factors, one with multiplicity two. check_factorization checks the product equation:

tutorial_factor.mojo Download
"""Factor a rational polynomial and verify its reconstruction."""
from std.testing import assert_equal, assert_true
from polynomials import Budget, QQ, NoContext, PolynomialRing, DensePoly, factor, check_factorization


def main() raises:
    var work = Budget()
    var ring = PolynomialRing[QQ].create(["x"], NoContext(), work)
    var polynomial = DensePoly[QQ].from_sparse(ring.parse("(x - 1)^2*(x + 2)", work), work, variable=Int64(0))
    var result = factor(polynomial, work)
    var verified = check_factorization(polynomial, result, work)
    assert_equal(len(result.factors), 2)
    assert_true(verified)
    print("Distinct factors:", len(result.factors))
    print("Product checked:", verified)

Run from the repository root pixi run mojo run -I build docs/examples/tutorial_factor.mojo

Output

Distinct factors: 2
Product checked: True

Conventions

Zero and constants have no factors; their scalar is the input constant. Squarefree blocks are monic and ordered by increasing multiplicity, over QQ, QQi and ModInt. factor_finite_field accepts arbitrary prime-field inputs and retains their leading scalar and multiplicities. The lower-level factor_mod_p keeps its original contract: a monic squarefree input, with invalid inputs rejected as DOMAIN. Both return factors independently of the supplied splitting seed.

factor_gaussian factors over QQi through exact conjugate norms. It returns monic factors sorted by degree, then coefficients from leading to constant, comparing real components before imaginary ones.

Integer factorization uses the first suitable prime from the fixed sequence, SplitMix64 seed 0, iterative Hensel correction digits, an exact conservative Landau–Mignotte bound, and recombination by exact trial division with subset and lattice-based paths. Integer factors are primitive with positive leading coefficients. Rational factors are monic. Recombination remains exponential in the worst case.

The two checkers prove the product equation. They do not certify irreducibility or squarefreeness; those are separate claims (Z-C1/Z-C2).

Algorithms

squarefree

def squarefree[C: CoefficientField](f: DensePoly[C], mut budget: Budget) raises PolyError -> SquarefreeDecomposition[C]

Decompose a polynomial into monic, pairwise coprime multiplicity blocks.

Parameters.

  • C: A characteristic-zero coefficient field or ModInt prime field.

Arguments.

  • f: The polynomial to decompose, including zero or constants.
  • budget: The shared work allowance.

Returns. The leading coefficient and nonconstant blocks in increasing multiplicity.

Raises.

  • PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/squarefree.mojo.

factor_mod_p

def factor_mod_p(f: DensePoly[ModInt], mut budget: Budget, seed: UInt64) raises PolyError -> List[DensePoly[ModInt]]

Factor a monic squarefree polynomial over its explicit prime field.

Arguments.

  • f: The monic squarefree input; one has an empty factor list.
  • budget: The shared work allowance.
  • seed: The SplitMix64 seed used for equal-degree splitting.

Returns. Monic irreducibles sorted by degree and coefficients from the leading one down.

Raises.

  • PolyError: DOMAIN for zero, nonmonic, nonsquarefree or malformed input, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/finite_field.mojo.

factor_integer

def factor_integer(f: DensePoly[ZZ], mut budget: Budget) raises PolyError -> Factorization[ZZ]

Factor an integer polynomial into primitive factors with positive leading coefficients.

Arguments.

  • f: The integer polynomial, including zero or constants.
  • budget: The shared work allowance.

Returns. Signed content and factors sorted by degree, then leading-to-constant coefficients.

Raises.

  • PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/factor.mojo.

factor

def factor(f: DensePoly[QQ], mut budget: Budget) raises PolyError -> Factorization[QQ]

Factor a rational polynomial into monic irreducibles with multiplicities.

Arguments.

  • f: The rational polynomial, including zero or constants.
  • budget: The shared work allowance.

Returns. The leading coefficient and factors in the deterministic coefficient order.

Raises.

  • PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/factor.mojo.

factor_finite_field

def factor_finite_field(f: DensePoly[ModInt], mut budget: Budget, seed: UInt64 = 0) raises PolyError -> Factorization[ModInt]

Factor any prime-field polynomial, including repeated and inseparable factors.

Arguments.

  • f: The input, including zero, constants and nonmonic polynomials.
  • budget: The shared work allowance.
  • seed: The deterministic equal-degree splitting seed; defaults to zero.

Returns. The leading coefficient and monic irreducibles with positive multiplicities, sorted by degree and then leading-to-constant residue vectors.

Raises.

  • PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/finite_field.mojo.

factor_gaussian

def factor_gaussian(f: DensePoly[QQi], mut budget: Budget) raises PolyError -> Factorization[QQi]

Factor over QQ(i) into monic irreducibles with exact multiplicities.

Arguments.

  • f: The Gaussian-rational polynomial, including zero and constants.
  • budget: The shared allowance for shifts, norms, rational factors and GCDs.

Returns. The leading coefficient and factors sorted by degree, then coefficients from leading to constant, comparing real before imaginary components.

Raises.

  • PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/gaussian_factor.mojo.

Certificates

SquarefreeDecomposition

@fieldwise_init
struct SquarefreeDecomposition[C: CoefficientRing](Copyable, Movable, Writable)

A scalar and monic squarefree blocks grouped by multiplicity.

Parameters.

  • C: The coefficient ring.

Defined in src/polynomials/certificates.mojo.

Field Type
unit Self.C The leading coefficient, or zero for the zero polynomial.
factors List[Tuple[DensePoly[Self.C], Int]] Nonconstant blocks and positive multiplicities, ordered by multiplicity.

Factorization

@fieldwise_init
struct Factorization[C: CoefficientRing](Copyable, Movable, Writable)

A scalar and normalized irreducible factors with multiplicities.

Parameters.

  • C: The coefficient ring.

Defined in src/polynomials/certificates.mojo.

Field Type
unit Self.C The scalar multiplier, including the sign over the integers.
factors List[Tuple[DensePoly[Self.C], Int]] Factors ordered by degree and then descending coefficient vectors.

check_squarefree_product

def check_squarefree_product[C: CoefficientRing](f: DensePoly[C], decomposition: SquarefreeDecomposition[C], mut budget: Budget) raises PolyError -> Bool

Check the squarefree product equation without claiming coprimality (Z-C1).

Parameters.

  • C: The coefficient ring.

Arguments.

  • f: The original polynomial.
  • decomposition: The scalar and proposed multiplicity blocks.
  • budget: The shared work allowance.

Returns. Whether the proposed product equals f.

Raises.

  • PolyError: DOMAIN for incompatible representations, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/certificates.mojo.

check_factorization

def check_factorization[C: CoefficientRing](f: DensePoly[C], factorization: Factorization[C], mut budget: Budget) raises PolyError -> Bool

Check the factor product equation without claiming irreducibility (Z-C2).

Parameters.

  • C: The coefficient ring.

Arguments.

  • f: The original polynomial.
  • factorization: The scalar and proposed factors with multiplicities.
  • budget: The shared work allowance.

Returns. Whether the proposed product equals f.

Raises.

  • PolyError: DOMAIN for incompatible representations, LIMIT or CAPACITY on work limits.

Defined in src/polynomials/certificates.mojo.