galois.Poly.equal_degree_factors(degree: int) list[Poly]

Factors the monic, square-free polynomial $$f(x)$$ of degree $$rd$$ into a product of $$r$$ irreducible factors with degree $$d$$.

Parameters:
degree: int

The degree $$d$$ of each irreducible factor of $$f(x)$$.

Returns:

The list of $$r$$ irreducible factors $$\{g_1(x), \dots, g_r(x)\}$$ in lexicographical order.

Raises:

ValueError – If $$f(x)$$ is not monic, has degree 0, or is not square-free.

The Equal-Degree Factorization algorithm factors a square-free polynomial $$f(x)$$ with degree $$rd$$ into a product of $$r$$ irreducible polynomials each with degree $$d$$. This function implements the Cantor-Zassenhaus algorithm, which is probabilistic.

The Equal-Degree Factorization algorithm is often applied after the Distinct-Degree Factorization algorithm, see distinct_degree_factors(). A complete polynomial factorization is implemented in factors().

Examples

Factor a product of degree-1 irreducible polynomials over $$\mathrm{GF}(2)$$.

In : a = galois.Poly([1, 0]); a, a.is_irreducible()
Out: (Poly(x, GF(2)), True)

In : b = galois.Poly([1, 1]); b, b.is_irreducible()
Out: (Poly(x + 1, GF(2)), True)

In : f = a * b; f
Out: Poly(x^2 + x, GF(2))

In : f.equal_degree_factors(1)
Out: [Poly(x, GF(2)), Poly(x + 1, GF(2))]


Factor a product of degree-3 irreducible polynomials over $$\mathrm{GF}(5)$$.

In : GF = galois.GF(5)

In : a = galois.Poly([1, 0, 2, 1], field=GF); a, a.is_irreducible()
Out: (Poly(x^3 + 2x + 1, GF(5)), True)

In : b = galois.Poly([1, 4, 4, 4], field=GF); b, b.is_irreducible()
Out: (Poly(x^3 + 4x^2 + 4x + 4, GF(5)), True)

In : f = a * b; f
Out: Poly(x^6 + 4x^5 + x^4 + 3x^3 + 2x^2 + 2x + 4, GF(5))

In : f.equal_degree_factors(3)
Out: [Poly(x^3 + 2x + 1, GF(5)), Poly(x^3 + 4x^2 + 4x + 4, GF(5))]