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

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 [1]: GF = galois.GF(5)

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

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

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

In [5]: f = a * b * c**3; f
Out[5]: 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 [6]: galois.square_free_factorization(f)
Out[6]: ([Poly(x^4 + 2x^2 + 4x, GF(5)), Poly(x^2 + 4x + 1, GF(5))], [1, 3])

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