galois.Poly.distinct_degree_factors() tuple[list[Poly], list[int]]

Factors the monic, square-free polynomial $$f(x)$$ into a product of polynomials whose irreducible factors all have the same degree.

Returns:

• The list of polynomials $$f_i(x)$$ whose irreducible factors all have degree $$i$$.

• The list of corresponding distinct degrees $$i$$.

Raises:

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

Notes

The Distinct-Degree Factorization algorithm factors a square-free polynomial $$f(x)$$ with degree $$d$$ into a product of $$d$$ polynomials $$f_i(x)$$, where $$f_i(x)$$ is the product of all irreducible factors of $$f(x)$$ with degree $$i$$.

$f(x) = \prod_{i=1}^{d} f_i(x)$

For example, suppose $$f(x) = x(x + 1)(x^2 + x + 1)(x^3 + x + 1)(x^3 + x^2 + 1)$$ over $$\mathrm{GF}(2)$$, then the distinct-degree factorization is

$\begin{split} f_1(x) &= x(x + 1) = x^2 + x \\ f_2(x) &= x^2 + x + 1 \\ f_3(x) &= (x^3 + x + 1)(x^3 + x^2 + 1) = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ f_i(x) &= 1\ \textrm{for}\ i = 4, \dots, 10. \end{split}$

Some $$f_i(x) = 1$$, but those polynomials are not returned by this function. In this example, the function returns $$\{f_1(x), f_2(x), f_3(x)\}$$ and $$\{1, 2, 3\}$$.

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

References

• Hachenberger, D. and Jungnickel, D. Topics in Galois Fields. Algorithm 6.2.2.

Examples

From the example in the notes, suppose $$f(x) = x(x + 1)(x^2 + x + 1)(x^3 + x + 1)(x^3 + x^2 + 1)$$ over $$\mathrm{GF}(2)$$.

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

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

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

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

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

In [6]: f = a * b * c * d * e; f
Out[6]: Poly(x^10 + x^9 + x^8 + x^3 + x^2 + x, GF(2))


The distinct-degree factorization is $$\{x(x + 1), x^2 + x + 1, (x^3 + x + 1)(x^3 + x^2 + 1)\}$$ whose irreducible factors have degrees $$\{1, 2, 3\}$$.

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

In [8]: [a*b, c, d*e], [1, 2, 3]
Out[8]:
([Poly(x^2 + x, GF(2)),
Poly(x^2 + x + 1, GF(2)),
Poly(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1, GF(2))],
[1, 2, 3])