AngouriMath

Symbolics for .NET


Table of contents

AngouriMath

Navigation
Home Quick start Wiki Almanac Research What's new Try Use Angouri.org GitHub Report a bug Donate Contacts

PolynomialFactorization

← Back to list of classes

Description

Summary

Factors a polynomial in one variable over the rationals into irreducibles:
x^4 + 3x^2 + 2 becomes (x^2 + 1)(x^2 + 2), which no search for roots can
find because it has none.

Remarks

This is what PolynomialFactoring is not. That one tries the candidates of
the rational root theorem and divides out the linear factors it finds, which answers
the question only when the polynomial splits into linear pieces. A factor of degree two
or more with no rational root is invisible to it, and those are the common case above
degree three.
 The route is Zassenhaus's, in four steps. Clear denominators and take the primitive
part, so the problem is over Z. Split off the repeated factors with
SquareFreeDecomposition, so every remaining problem is square-free.
Factor what is left modulo a small prime, where
Berlekamp answers completely and cheaply.
Then lift that factorisation from p to p^k by Hensel's construction and
try products of the lifted pieces against the original, which is where the true
factors are recovered — an irreducible factor over Z may well split further
modulo p, so the modular factors have to be recombined rather than read off.
Zassenhaus, On Hensel factorization I, J. Number Theory 1 (1969); von zur Gathen
and Gerhard, Modern Computer Algebra, ch. 15.
 Two things bound the cost, and both are refusals rather than approximations. The
recombination is exponential in the number of modular factors, so it is given a budget
and declines past it. And k is chosen from Mignotte's bound so that a
coefficient in the symmetric range modulo p^k is the coefficient itself; a
smaller k would not make an answer wrong, since every candidate is confirmed by
exact division over Z before it is accepted, but it would make the search miss
factors and call a reducible polynomial irreducible.
 Nothing here is trusted. Every candidate factor is divided out exactly over Z,
and the factors are multiplied back and compared with what they came from before the
answer is returned. The failure mode that survives all of that is an incomplete
factorisation, never a wrong one.

Members

























Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 4378 pages online