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.

jverzani / PolynomialFactors.jl

readme

PolynomialFactors