galois.poly_factors

galois.poly_factors(poly)

Factors the polynomial \(f(x)\) into a product of irreducible factors \(f(x) = g_1(x)^{e_1} g_2(x)^{e_2} \dots g_k(x)^{e_k}\).

This function implements the Square-Free Factorization algorithm.

Parameters

poly (galois.Poly) – The polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\) to be factored.

Returns

  • list – The list of \(k\) polynomial factors \(\{g_1(x), g_2(x), \dots, g_k(x)\}\) sorted in increasing lexicographic order.

  • list – The list of corresponding multiplicities \(\{e_1, e_2, \dots, e_k\}\).

References

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

Examples

In [1]: GF = galois.GF2

# Ensure the factors are irreducible by using Conway polynomials
In [2]: g1, g2, g3 = galois.conway_poly(2, 3), galois.conway_poly(2, 4), galois.conway_poly(2, 5)

In [3]: g1, g2, g3
Out[3]: 
(Poly(x^3 + x + 1, GF(2)),
 Poly(x^4 + x + 1, GF(2)),
 Poly(x^5 + x^2 + 1, GF(2)))

In [4]: e1, e2, e3 = 4, 3, 2

# Construct the composite polynomial
In [5]: f = g1**e1 * g2**e2 * g3**e3

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

In [7]: GF = galois.GF(3)

# Ensure the factors are irreducible by using Conway polynomials
In [8]: g1, g2, g3 = galois.conway_poly(3, 3), galois.conway_poly(3, 4), galois.conway_poly(3, 5)

In [9]: g1, g2, g3
Out[9]: 
(Poly(x^3 + 2x + 1, GF(3)),
 Poly(x^4 + 2x^3 + 2, GF(3)),
 Poly(x^5 + 2x + 1, GF(3)))

In [10]: e1, e2, e3 = 5, 4, 3

# Construct the composite polynomial
In [11]: f = g1**e1 * g2**e2 * g3**e3

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