galois.poly_factors¶

class galois.poly_factors(poly)¶

Factors the polynomial \(f(x)\) into a product of \(n\) irreducible factors \(f(x) = g_0(x)^{k_0} g_1(x)^{k_1} \dots g_{n-1}(x)^{k_{n-1}}\) with \(k_0 \le k_1 \le \dots \le k_{n-1}\).

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 \(n\) polynomial factors \(\{g_0(x), g_1(x), \dots, g_{n-1}(x)\}\).
list – The list of \(n\) polynomial multiplicities \(\{k_0, k_1, \dots, k_{n-1}\}\).

References

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

Examples

In [583]: GF = galois.GF2

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

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

In [586]: k0, k1, k2 = 2, 3, 4

# Construct the composite polynomial
In [587]: f = g0**k0 * g1**k1 * g2**k2

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

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

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

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

In [592]: k0, k1, k2 = 3, 4, 6

# Construct the composite polynomial
In [593]: f = g0**k0 * g1**k1 * g2**k2

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