# galois.equal_degree_factorization¶

galois.equal_degree_factorization(poly, degree)

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

Parameters
• poly (galois.Poly) – A monic, square-free polynomial $$f(x)$$ over $$\mathrm{GF}(p^m)$$.

• 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 lexicographically-increasing order.

Return type

list

Notes

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 galois.distinct_degree_factorization(). A complete polynomial factorization is implemented in galois.factors().

References

Examples

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

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

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

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

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


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

In [5]: GF = galois.GF(5)

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

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

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

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