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, 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])