# 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

1. Hachenberger, D. Jungnickel. 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 : a = galois.Poly([1,0]); a, galois.is_irreducible(a)
Out: (Poly(x, GF(2)), True)

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

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

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

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

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