galois.Poly.square_free_factors

galois.Poly.square_free_factors() → tuple[list[Poly], list[int]]

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

Returns:¶

The list of non-constant, square-free polynomials $h_{j} (x)$ in the factorization.
The list of corresponding multiplicities $j$ .

Raises:¶

ValueError – If $f (x)$ is not monic or has degree 0.

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 factors().

References¶

Hachenberger, D. and Jungnickel, D. Topics in Galois Fields. Algorithm 6.1.7.
Section 2.1 from https://people.csail.mit.edu/dmoshkov/courses/codes/poly-factorization.pdf

Examples¶

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

In [1]: GF = galois.GF(5)

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

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

In [4]: c = galois.Poly([1,4,1], field=GF); c, c.is_irreducible()
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} + 2 x + 4), x^{2} + 4 x + 1}$ with multiplicities ${1, 3}$ .

In [6]: f.square_free_factors()
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])