galois.Poly.factors() tuple[list[Poly], list[int]]

Computes the irreducible factors of the non-constant, monic polynomial $$f(x)$$.

Returns:

• Sorted list of irreducible factors $$\{g_1(x), g_2(x), \dots, g_k(x)\}$$ of $$f(x)$$ sorted in lexicographical order.

• List of corresponding multiplicities $$\{e_1, e_2, \dots, e_k\}$$.

Raises:

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

This function factors a monic polynomial $$f(x)$$ into its $$k$$ irreducible factors such that $$f(x) = g_1(x)^{e_1} g_2(x)^{e_2} \dots g_k(x)^{e_k}$$.

Steps:

1. Apply the Square-Free Factorization algorithm to factor the monic polynomial into square-free polynomials. See square_free_factors().

2. Apply the Distinct-Degree Factorization algorithm to factor each square-free polynomial into a product of factors with the same degree. See distinct_degree_factors().

3. Apply the Equal-Degree Factorization algorithm to factor the product of factors of equal degree into their irreducible factors. See equal_degree_factors().

• Hachenberger, D. and Jungnickel, D. Topics in Galois Fields. Algorithm 6.1.7.

Examples

Generate irreducible polynomials over $$\mathrm{GF}(3)$$.

In : GF = galois.GF(3)

In : g1 = galois.irreducible_poly(3, 3); g1
Out: Poly(x^3 + 2x + 1, GF(3))

In : g2 = galois.irreducible_poly(3, 4); g2
Out: Poly(x^4 + x + 2, GF(3))

In : g3 = galois.irreducible_poly(3, 5); g3
Out: Poly(x^5 + 2x + 1, GF(3))


Construct a composite polynomial.

In : e1, e2, e3 = 5, 4, 3

In : f = g1**e1 * g2**e2 * g3**e3; f
Out: Poly(x^46 + x^44 + 2x^41 + x^40 + 2x^39 + 2x^38 + 2x^37 + 2x^36 + 2x^34 + x^33 + 2x^32 + x^31 + 2x^30 + 2x^29 + 2x^28 + 2x^25 + 2x^24 + 2x^23 + x^20 + x^19 + x^18 + x^15 + 2x^10 + 2x^8 + x^5 + x^4 + x^3 + 1, GF(3))


Factor the polynomial into its irreducible factors over $$\mathrm{GF}(3)$$.

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