Skip to content

Factor

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

Factor[poly]

factors a polynomial over the integers.

Factor[poly, Extension -> alpha]

factors over Q(alpha), where alpha is

Sqrt[c], c^(1/n) (rational c), or I. Implements Trager's algebraic-

Factor[poly, Extension -> {alpha_1, ..., alpha_n}]

factors over the

Notes factoring algorithm via norm + sqfr\_norm + alg\_factor. compositum Q(alpha\_1, ..., alpha\_n). The tower is reduced to a single primitive element gamma = alpha\_1 + s\_2 alpha\_2 + ... via Trager's primitive-element algorithm (Phase G6).

Examples (21)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (6)

In[1]:= Factor[1 + 2x + x^2]
Out[1]= (1 + x)^2

In[2]:= Factor[x^10 - 1]
Out[2]= (-1 + x) (1 + x) (1 + x + x^2 + x^3 + x^4) (1 - x + x^2 - x^3 + x^4)

In[3]:= Factor[x^10 - y^10]
Out[3]= (x + y) (x - y) (x^4 + x^3 y + x^2 y^2 + x y^3 + y^4) (x^4 - x^3 y + x^2 y^2 - x y^3 + y^4)

In[4]:= Factor[2x^3 y - 2a^2 x y - 3a^2 x^2 + 3a^4]
Out[4]= (a + x) (a - x) (3 a^2 - 2 x y)

In[5]:= Factor[(x^3 + 2x^2)/(x^2 - 4y^2) - (x + 2)/(x^2 - 4y^2)]
Out[5]= ((-1 + x) (1 + x) (2 + x))/((x - 2 y) (x + 2 y))

In[6]:= Factor[Integrate[f[x], x] x^2 - Integrate[f[x], x]]
Out[6]= (-1 + x) (1 + x) Integrate[f[x], x]

Options (2)

In[7]:= Factor[x^4 + 1, Modulus -> 3]
Out[7]= (2 + x + x^2) (2 + 2 x + x^2)

In[8]:= Factor[x^4 + 1, Extension -> Sqrt[2]]
Out[8]= (1 + Sqrt[2] x + x^2) (1 - Sqrt[2] x + x^2)

Worked examples (3)

In[9]:= Factor[y^2 - x^2]
Out[9]= -(x + y) (x - y)

In[10]:= Factor[E^x (x^2 - 1)]
Out[10]= E^x (-1 + x) (1 + x)

In[11]:= Factor[Log[x] (x^2 - 1)]
Out[11]= Log[x] (-1 + x) (1 + x)

Applications (10)

Factorisation over the integers with a non-monic leading coefficient

In[12]:= Factor[6 x^2 + 7 x + 2]
Out[12]= (1 + 2 x) (2 + 3 x)

Cyclotomic factors of x^10 - 1

In[13]:= Factor[x^10 - 1]
Out[13]= (-1 + x) (1 + x) (1 + x + x^2 + x^3 + x^4) (1 - x + x^2 - x^3 + x^4)

The multivariate FLINT path: one factor for each divisor of 99

In[14]:= Length[Factor[x^99 - y^99]]
Out[14]= 6

A rational function: combined first, then numerator and denominator factored

In[15]:= Factor[(x^3 + 2 x^2)/(x^2 - 4 y^2) - (x + 2)/(x^2 - 4 y^2)]
Out[15]= ((-1 + x) (1 + x) (2 + x))/((x - 2 y) (x + 2 y))

An irreducible quartic splits over Q(Sqrt[2])

In[16]:= Factor[x^4 + 1, Extension -> Sqrt[2]]
Out[16]= (1 + Sqrt[2] x + x^2) (1 - Sqrt[2] x + x^2)

A tower of extensions, reduced to one primitive element

In[17]:= Factor[x^4 - 5 x^2 + 6, Extension -> {Sqrt[2], Sqrt[3]}]
Out[17]= (Sqrt[2] + x) (Sqrt[3] + x) (-Sqrt[2] + x) (-Sqrt[3] + x)

The extension is detected from the coefficients

In[18]:= Factor[x^2 - 2 Sqrt[2] x + 2, Extension -> Automatic]
Out[18]= (-Sqrt[2] + x)^2

Factorisation in F_3[x]

In[19]:= Factor[x^4 + 1, Modulus -> 3]
Out[19]= (2 + x + x^2) (2 + 2 x + x^2)

A polynomial in the kernel E^x

In[20]:= Factor[E^(2 x) - 1]
Out[20]= (-1 + E^x) (1 + E^x)

An unevaluated integral is carried as an opaque factor

In[21]:= Factor[Integrate[f[x], x] x^2 - Integrate[f[x], x]]
Out[21]= (-1 + x) (1 + x) Integrate[f[x], x]

Performance

Against other systems, from the benchmark suite (same input, results cross-checked for agreement):

case Mathilda Wolfram Python
GroebnerBasis cyclic-5 43.5 s 18 s 8.78e+03 s
Factor x^120 - 1 7.01 s 0.044 s 3.85 s
Discriminant of deg 20 2.51 s 0.068 s 0.182 s
Factor dense degree 60 2.2 s 0.599 s 26.5 s
Factor product of 16 quadratics 1.29 s 0.722 s 27.6 s
Factor sparse degree 60 0.532 s 0.516 s 9.48 s

Implementation notes

Algorithm. builtin_factor lives in src/poly/facpoly.c, which is assembled from a set of .inc fragments (squarefree, Berlekamp–Zassenhaus univariate, bivariate/trivariate Hensel, the heuristic dispatcher, the memo cache, and the builtin entry point). The entry point (facpoly_factor_builtin.inc) is a cascade:

  1. Modulus and FLINT fast paths. Modulus -> p factors in F_p[x] through flint_nmod_poly_factor_list. The classical path declines on a composite or non-word modulus or on several variables, rather than ignoring the option. A free-symbol radicand Sqrt[k] is factored over Q(t…)(Sqrt[k]) by flint_parametric_sqrt_factor. Once the memo and inexact checks pass, a univariate polynomial over Z goes to flint_univariate_factor_auto (fmpz_poly_factor, bignum-safe), and a multivariate polynomial over Q given as one plain argument goes to flint_polynomial_factor (fmpq_mpoly_factor; x^99 - y^99 takes milliseconds). Both emit primitive, positive-leading factors and decline on any non-polynomial head, which then takes the classical cascade below.
  2. Options / algebraic extensions. A trailing Extension -> α (or -> Automatic, autodetected via extension_autodetect, or a List tower) routes to the algebraic-number factorer in qafactor.c (Trager's algorithm over Q(α)). The Simplify-scoped result memo (factor_memo_*) is bypassed in this branch.
  3. Memo + inexact handling. A per-Simplify result cache is consulted; inexact coefficients are sent through internal_rationalize_then_numericalize.
  4. Threading. Factor is LISTABLE; comparison/logic heads (Less, Equal, Inequality, And, …) are hand-threaded elementwise.
  5. Radical generators. If the input contains a fractional-power sub-expression u^{p/q}, it substitutes u → g^m (m = lcm of the q's), factors as a polynomial in g, and back-substitutes. Since v0.434 this substitution (poly_subst_radical_to_gen) treats binding operators (poly_is_binding_operator: unevaluated Integrate, D, Sum, Hold*, …) as opaque atoms, so a factor such as Integrate[f[x], x] is carried through untouched.
  6. Rational normalisation. Together → split into Numerator/Denominator; each is factored independently (in a direct call) or with a shared variable scope (inside Simplify).

The numerator/denominator are factored by variable count: univariate → bz_factor_to_expr (the Berlekamp–Zassenhaus pipeline, facpoly_bz_uni.inc); bivariate → a direct bivariate Hensel lift fast path (factor_bivariate_via_hensel), falling back to FactorSquareFree + heuristic_factor; ≥ 3 variables → FactorSquareFree followed by heuristic_factor's recursive per-piece dispatch.

The univariate Berlekamp–Zassenhaus core (factor_zassenhaus): take the primitive part, pick a prime p (starting at 13) under which the polynomial stays square-free, factor mod p by distinct-degree (cz_ddf) then equal-degree (cz_edf) Cantor–Zassenhaus splitting, Hensel-lift the modular factors to p^k (multifactor_hensel_lift/hensel_lift) with p^k chosen large, then recombine by brute-force subset enumeration over the lifted factors — each candidate true factor is reconstructed with leading-coefficient and content correction and accepted when upoly_div_exact_z divides the remaining polynomial exactly.

Data structures. The univariate path uses a packed UPoly { int deg; int64_t* c; } with __int128_t-guarded modular arithmetic (upoly_mul_mod, upoly_div_rem_mod, upoly_gcd_mod, mod_inverse_int) and UPolyList collections. Multivariate paths use Expr* polynomials plus the MPoly/BPoly representations from mpoly.c/bpoly.c for Hensel lifting. The algebraic path uses QATower from qafactor.c.

Complexity / limits. With FLINT, plain integer and rational polynomials take the FLINT factorers, and the classical engine below handles the remaining cases. Modular coefficients are carried in int64/int128, so the chosen p^k is bounded below 10^15. Since v0.434 the trial division upoly_div_exact_z checks every multiply and subtract for overflow (ci_mul_i64/ci_sub_i64) and skips a candidate divisor that would overflow. Skipping leaves a coarser but still exact factorisation; before the fix the corrupted remainder trapped with SIGFPE. the Zassenhaus recombination is exponential in the number of modular factors (the classical worst case). The integer-arithmetic UPoly path caps degree at 10000. Multivariate factoring is heuristic (heuristic_factor) rather than a complete algorithm.

  • Listable, Protected.
  • FLINT acceleration (when built with FLINT): a univariate polynomial over Z is factored via fmpz_poly_factor, and a genuine multivariate polynomial over Q via fmpq_mpoly_factor, both from a guarded fast path at the top of builtin_factor (plain single-argument form only). This turns the exponential-in-variable-count classical multivariate factoriser — which hangs on inputs like Factor[x^99 - y^99] (> 20 s) — into a few-millisecond call. Each irreducible factor is normalised to a positive leading coefficient (highest total degree, deglex tie-break — the conventional normalisation), with the discarded sign folded into a separated rational content, so e.g. Factor[y^2 - x^2] → -(x - y)(x + y). Inputs that are not a polynomial over Q (a denominator, fractional/symbolic exponent, or a non-polynomial head such as Sqrt/Sin) fall through to the classical path unchanged; Extension/GaussianIntegers/Modulus option forms travel their own branch and are untouched. See also the FLINT`Factor builtin.
  • When given a rational expression, first resolves dependencies over Together before factoring.
  • Uses exact root isolation (Rational Root Theorem limits) and binomial descents structured identically to Zassenhaus recombination, evaluating combinations exact and memory safe.
  • Threads natively across lists, logic structures, and numeric groupings perfectly.
  • Bivariate inputs whose leading coefficient (in some variable) is the constant -1 are handled via Wang's leading-coefficient correction, Stage 1: the input is pre-negated to make it monic, the existing monic Hensel pipeline runs on -P, and the overall sign is absorbed into the highest-degree factor via Expand. This unlocks inputs of shape Factor[(1 - x^k)(x - y^m)] (and similar non-monic cases with constant ±1 LC) that previously fell back to the legacy linear-trial-division loop.
  • Bivariate inputs whose leading coefficient (in some variable) is a non-unit integer constant a (with |a| > 1) are handled via Wang's leading-coefficient correction, Stage 2: the monic substitution Q(x, y) = a^(d-1) · P(x/a, y) makes the lift's input monic in x with integer coefficients. After lifting Q = G_1 · ... · G_r via the existing pipeline, the true factors of P are recovered as F_i = G_i(a·x, y) / cont_Z(G_i(a·x, y)), where the integer content collects exactly the share of a^(d-1) redistributed into G_i by the substitution. Stages 1 and 2 compose, so inputs with negative non-unit LC (e.g. lc_x(P) = -6) also enter the structured pipeline. This unlocks inputs like Factor[Expand[(2x+3y)(3x+5y)]], Factor[2 a^2 - 5 a b + 3 b^2], and three-factor non-monic forms whose LCs are constant in y (or constant in x).
  • Bivariate inputs whose leading coefficient (in some variable) is a non-constant polynomial in the other variable are handled via Wang's leading-coefficient correction, Stage 3 (predicted-LC two-factor Hensel). When lc_x(P)(y) = A(y), Mathilda factors A over Z[y], finds α with A(α) = +1 so the squarefree univariate image P(x, α) factors into monic Z[x] pieces u, v, then enumerates distributions of A's irreducible factors between two predicted leading coefficients q_u, q_v (with q_u · q_v = A and q_u(α) = q_v(α) = +1). The Hensel iteration is modified so each Δu correction has its leading-x coefficient PINNED to the y^k coefficient of q_u, keeping lc_x(U)(y) = q_u(y) invariant across the lift. This unlocks inputs like Factor[Expand[(xy+1)(xy+2)]], Factor[Expand[((y²+1)x+1)(x+3)]], Factor[Expand[((y+1)x+1)((y+1)x+2)]]. MVP scope: r = 2 (two univariate factors), both monic, |cont(A)| = 1, and inputs with non-trivial monomial content fall through so heuristic_factor's Phase 0 path produces the canonical fully-factored form.
  • Binomial-descent soundness. The heuristic two-term a^k ± b^k descent fires only when both terms of the Plus parse as genuine polynomial monomials (an integer times variables and integer powers). A term with a non-polynomial head — Cos[r^2], r^2 Sin[r^2], a generic f[r^2] — is no longer misread as the bare constant 1. Previously the monomial parse silently dropped such factors, so Factor[Cos[r^2] - r^2] returned the unsound -(-1 + r)(1 + r), and, because Simplify runs Factor as a candidate and keeps the shorter form, Simplify[Laplacian[Sin[r^2], {r, t}, "Polar"]] collapsed to 4 - 4 r^2. Such inputs are now returned unfactored.
  • A product never comes back as a sum. Factor normalises through Together, and Together expands a multivariate product: Together[E^x (x^2 - 1)] is -E^x + x^2 E^x. That expansion is not a polynomial in the single variable collect_variables finds (x) — its coefficients carry E^x — so there was nothing to factor and the expansion came straight back: Factor[E^x (x^2 - 1)] returned -E^x + x^2 E^x, less factored than its own input, and Integrate[x^5 E^x, x] // Factor multiplied the integrator's answer out. Factoring is multiplicative, so a denominator-free product is now factored factor by factor: Factor[E^x (x^2 - 1)] → E^x (-1 + x) (1 + x), Factor[Log[x] (x^2 - 1)] → (-1 + x) (1 + x) Log[x], and an irreducible polynomial factor is returned whole rather than expanded. The denominator case is deliberately excluded, because a sum is the right answer there: Factor[(x^2 - 1)/(x - 1)] is 1 + x, and threading over that Times would hand back an uncancelled (x - 1) (x + 1)/(x - 1). Under that guard the rewrite fires only where the polynomial path has already failed, so nothing that factors today changes route. (The root defect is Together's expansion, left alone here: a great deal of the integrator, DSolve and Simplify is tuned around the shape it returns.)
  • Uncombined-fraction soundness. Factor derives its numerator/denominator from Together, then factors each as a polynomial. When Together declines to combine a sum of fractions (notably a sum whose numerators share ≥2 dependent trig/hyperbolic kernels over Q(i), which Together leaves uncombined to avoid a GCD blow-up), the "numerator" is still a Plus carrying Power[linear, -1] denominators — not a polynomial. Feeding it to the polynomial factorer treated 1/(x - I) as an indeterminate and returned a non-equivalent result: Factor[(-1/2*I) (Cosh[x] + Sinh[x])/(-I + x) + (1/2*I) (Cosh[x] + Sinh[x])/(I + x)] collapsed to 0, which (via the same Simplify-trusts-Factor path) made D[Integrate[Exp[x]/(x^2 + 1), x], x] // Simplify return 0 instead of E^x/(1 + x^2). Factor now verifies the numerator/denominator are genuinely denominator-free before factoring and, when they are not, returns the input unchanged rather than a false factorisation. The well-combined cases (polynomials, single-trig, symbol sums, real-denominator sums, f[x] + g[x], Gaussian-integer polynomials) are unaffected.

Attributes: Listable, Protected.

References

See also: Sqrt, Sin, Modulus, Together, Expand, Plus, Simplify, Times

  • B. M. Trager, "Algebraic factoring and rational function integration", SYMSAC 1976 — the norm / sqfr_norm / alg_factor approach used for the Extension path.
  • Geddes, Czapor & Labahn, "Algorithms for Computer Algebra" (1992), Ch. 8 (polynomial factorization).
  • H. Zassenhaus, "On Hensel factorization, I", J. Number Theory 1969.
  • D. G. Cantor, H. Zassenhaus, "A new algorithm for factoring polynomials over finite fields", Math. Comp. 1981.
  • D. Y. Y. Yun, "On square-free decomposition algorithms", SYMSAC 1976.
  • K. O. Geddes, S. R. Czapor, G. Labahn, Algorithms for Computer Algebra (Kluwer, 1992).
  • B. M. Trager, "Algebraic factoring and rational function integration", SYMSAC 1976.
  • Source: src/poly/facpoly.c
  • Specification: docs/spec/builtins/structural-manipulation.md
  • Tests: tests/test_cherry_dilog.c
  • Tests: tests/test_cherry_dilog_exp.c
  • Tests: tests/test_cherry_polylog_exp.c
  • Tests: tests/test_cherry_stress.c

Notes & additional examples

Notes

  • Over the integers, Factor returns irreducible factors with the integer content pulled out front. x^2 + 1 stays as it is because it has no rational factors. Factors print in canonical term order, constant term first (-1 + x, not x - 1).
  • Engines. With FLINT, univariate integer polynomials go to fmpz_poly_factor and multivariate rational polynomials to fmpq_mpoly_factor. Otherwise the native Berlekamp–Zassenhaus and Hensel code runs, with heuristics for three or more variables. Extension -> α (or a list, or Automatic) factors over the number field with Trager's algorithm. Modulus -> p factors over F_p. A composite modulus is left unevaluated.
  • Rational functions and kernels. A rational expression is combined with Together first. Exponentials, trig functions and fractional powers are factored as polynomials in their kernels. Unevaluated Integrate, D and Sum are opaque atoms.
  • Threading. Listable, and threads over equations, inequalities and logical connectives as well.
  • Protected. Symbolic only.
  • See also: FactorList, FactorSquareFree, FactorTerms, Expand, Together, FactorInteger.