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

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
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]: c = galois.Poly([1, 1, 1]); c
Out[5]: Poly(x^2 + x + 1, GF(2))

In [6]: assert c.is_irreducible()

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

In [8]: assert d.is_irreducible()

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

In [10]: assert e.is_irreducible()

In [11]: f = a * b * c * d * e; f
Out[11]: 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 [12]: f.distinct_degree_factors()
Out[12]: 
([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 [13]: [a*b, c, d*e], [1, 2, 3]
Out[13]: 
([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])