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.

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

References¶

• Section 2.3 from https://people.csail.mit.edu/dmoshkov/courses/codes/poly-factorization.pdf

• Section 1 from https://www.csa.iisc.ac.in/~chandan/courses/CNT/notes/lec8.pdf

Examples¶

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

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

In [2]: assert a.is_irreducible()

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

In [4]: assert b.is_irreducible()

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

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

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

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

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

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

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

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