# galois.square_free_factorization¶

galois.square_free_factorization(poly)

Factors the monic polynomial $$f(x)$$ into a product of square-free polynomials.

Parameters

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

Returns

• list – The list of non-constant, square-free polynomials $$h_i(x)$$ in the factorization.

• list – The list of corresponding multiplicities $$i$$.

Notes

The Square-Free Factorization algorithm factors $$f(x)$$ into a product of $$m$$ square-free polynomials $$h_j(x)$$ with multiplicity $$j$$.

$f(x) = \prod_{j=1}^{m} h_j(x)^j$

Some $$h_j(x) = 1$$, but those polynomials are not returned by this function.

A complete polynomial factorization is implemented in galois.factors().

References

1. Hachenberger, D. Jungnickel. Topics in Galois Fields. Algorithm 6.1.7.

Examples

Suppose $$f(x) = x(x^3 + 2x + 4)(x^2 + 4x + 1)^3$$ over $$\mathrm{GF}(5)$$. Each polynomial $$x$$, $$x^3 + 2x + 4$$, and $$x^2 + 4x + 1$$ are all irreducible over $$\mathrm{GF}(5)$$.

In : GF = galois.GF(5)

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

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

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

In : f = a * b * c**3; f
Out: Poly(x^10 + 2x^9 + 3x^8 + x^7 + x^6 + 2x^5 + 3x^3 + 4x, GF(5))


The square-free factorization is $$\{x(x^3 + 2x + 4), x^2 + 4x + 1\}$$ with multiplicities $$\{1, 3\}$$.

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

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