PolynomialFactors
A package for factoring polynomials with integer or rational coefficients over the integers.
For polynomials over the integers or rational numbers, this package provides

a
factor
command to factor into irreducible factors over the integers; 
a
rational_roots
function to return the rational roots; 
a
powermod
function to factor the polynomial over Z/pZ.
The implementation is based on the CantorZassenhaus approach, as detailed in Chapters 14 and 15 of the excellent text Modern Computer Algebra by von zer Gathen and Gerhard and a paper by Beauzamy, Trevisan, and Wang.
The factoring solutions in SymPy.jl
or Nemo.jl
would be preferred,
in general, especially for larger problems (degree 30 or more, say) where the performance here is not good. However, this package
requires no additional external libraries. (PRs improving performance are most welcome.)
Examples:
julia> using AbstractAlgebra, PolynomialFactors;
julia> R, x = ZZ["x"];
julia> p = prod(x .[1,1,3,3,3,3,5,5,5,5,5,5])
x^1244*x^11+874*x^1010348*x^9+81191*x^8443800*x^7+1728556*x^64818680*x^5+9505375*x^412877500*x^3+11306250*x^25737500*x+1265625
julia> poly_factor(p)
Dict{AbstractAlgebra.Generic.Poly{BigInt},Int64} with 3 entries:
x5 => 6
x1 => 2
x3 => 4
As can be seen factor
returns a dictionary whose keys are
irreducible factors of the polynomial p
as Polynomial
objects, the
values being their multiplicity. If the polynomial is nonmonic, a
degree $0$ polynomial is there so that the original polynomial can be
recovered as the product prod(k^v for (k,v) in poly_factor(p))
.
Here we construct the polynomial in terms of a variable x
:
julia> poly_factor((x1)^2 * (x3)^4 * (x5)^6)
Dict{AbstractAlgebra.Generic.Poly{BigInt},Int64} with 3 entries:
x5 => 6
x1 => 2
x3 => 4
Factoring over the rationals is really done over the integers, The first step is to find a common denominator for the coefficients. The constant polynomial term reflects this.
julia> R, x = QQ["x"]
(Univariate Polynomial Ring in x over Rationals, x)
julia> poly_factor( (1//2  x)^2 * (1//3  1//4 * x)^5 )
Dict{AbstractAlgebra.Generic.Poly{Rational{BigInt}},Int64} with 3 entries:
2//1*x1//1 => 2
3//1*x4//1 => 5
1//995328 => 1
For some problems big integers are necessary to express the problem:
julia> p = prod(x . collect(1:20))
x^20210*x^19+20615*x^181256850*x^17+53327946*x^161672280820*x^15+40171771630*x^14756111184500*x^13+11310276995381*x^12135585182899530*x^11+1307535010540395*x^1010142299865511450*x^9+63030812099294896*x^8311333643161390640*x^7+1206647803780373360*x^63599979517947607200*x^5+8037811822645051776*x^412870931245150988800*x^3+13803759753640704000*x^28752948036761600000*x+2432902008176640000
julia> poly_factor(p)
Dict{AbstractAlgebra.Generic.Poly{BigInt},Int64} with 20 entries:
x15 => 1
x18 => 1
x17 => 1
x9 => 1
x5 => 1
x14 => 1
x7 => 1
x13 => 1
x11 => 1
x2 => 1
x12 => 1
x1 => 1
x3 => 1
x8 => 1
x10 => 1
x4 => 1
x19 => 1
x16 => 1
x6 => 1
x20 => 1
julia> poly_factor(x^2  big(2)^256)
Dict{AbstractAlgebra.Generic.Poly{BigInt},Int64} with 2 entries:
x+340282366920938463463374607431768211456 => 1
x340282366920938463463374607431768211456 => 1
Factoring polynomials over a finite field of coefficients, Z_p[x]
with p
a prime, is also provided by factormod
:
julia> factormod(x^4 + 1, 2)
Dict{AbstractAlgebra.Generic.Poly{AbstractAlgebra.gfelem{BigInt}},Int64} with 1 entry:
x+1 => 4
julia> factormod(x^4 + 1, 5)
Dict{AbstractAlgebra.Generic.Poly{AbstractAlgebra.gfelem{BigInt}},Int64} with 2 entries:
x^2+3 => 1
x^2+2 => 1
julia> factormod(x^4 + 1, 3)
Dict{AbstractAlgebra.Generic.Poly{AbstractAlgebra.gfelem{BigInt}},Int64} with 2 entries:
x^2+x+2 => 1
x^2+2*x+2 => 1
julia> factormod(x^4 + 1, 7)
Dict{AbstractAlgebra.Generic.Poly{AbstractAlgebra.gfelem{BigInt}},Int64} with 2 entries:
x^2+3*x+1 => 1
x^2+4*x+1 => 1
The keys are polynomials a finite group, not over the integers.