galois.distinct_degree_factorization

galois.distinct_degree_factorization(poly)

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

Parameters

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

Returns

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

  • list – The list of corresponding distinct degrees \(i\).

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{align}\begin{aligned}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{aligned}\end{align} \]

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 galois.square_free_factorization(). A complete polynomial factorization is implemented in galois.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, 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]: c = galois.Poly([1,1,1]); c, galois.is_irreducible(c)
Out[3]: (Poly(x^2 + x + 1, GF(2)), True)

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

In [5]: e = galois.Poly([1,1,0,1]); e, galois.is_irreducible(e)
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]: galois.distinct_degree_factorization(f)
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])