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 Cantor-Zassenhaus 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^12-44*x^11+874*x^10-10348*x^9+81191*x^8-443800*x^7+1728556*x^6-4818680*x^5+9505375*x^4-12877500*x^3+11306250*x^2-5737500*x+1265625

julia> poly_factor(p)
Dict{AbstractAlgebra.Generic.Poly{BigInt},Int64} with 3 entries:
  x-5 => 6
  x-1 => 2
  x-3 => 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 non-monic, 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((x-1)^2 * (x-3)^4 * (x-5)^6)
Dict{AbstractAlgebra.Generic.Poly{BigInt},Int64} with 3 entries:
  x-5 => 6
  x-1 => 2
  x-3 => 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*x-1//1 => 2
  3//1*x-4//1 => 5
  -1//995328  => 1

For some problems big integers are necessary to express the problem:

julia> p = prod(x .- collect(1:20))
x^20-210*x^19+20615*x^18-1256850*x^17+53327946*x^16-1672280820*x^15+40171771630*x^14-756111184500*x^13+11310276995381*x^12-135585182899530*x^11+1307535010540395*x^10-10142299865511450*x^9+63030812099294896*x^8-311333643161390640*x^7+1206647803780373360*x^6-3599979517947607200*x^5+8037811822645051776*x^4-12870931245150988800*x^3+13803759753640704000*x^2-8752948036761600000*x+2432902008176640000

julia> poly_factor(p)
Dict{AbstractAlgebra.Generic.Poly{BigInt},Int64} with 20 entries:
  x-15 => 1
  x-18 => 1
  x-17 => 1
  x-9  => 1
  x-5  => 1
  x-14 => 1
  x-7  => 1
  x-13 => 1
  x-11 => 1
  x-2  => 1
  x-12 => 1
  x-1  => 1
  x-3  => 1
  x-8  => 1
  x-10 => 1
  x-4  => 1
  x-19 => 1
  x-16 => 1
  x-6  => 1
  x-20 => 1

julia> poly_factor(x^2 - big(2)^256)
Dict{AbstractAlgebra.Generic.Poly{BigInt},Int64} with 2 entries:
  x+340282366920938463463374607431768211456 => 1
  x-340282366920938463463374607431768211456 => 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.

Reference

factormod(q::AbstractAlgebra.Generic.Poly{T}, p)

poly_factor(p::AbstractAlgebra.Generic.Poly{T})