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 lexicographically-increasing order.

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

Raises¶

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

Notes¶

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

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¶

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

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

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

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

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

Construct a composite polynomial.

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

In [6]: f = g1**e1 * g2**e2 * g3**e3; f
Out[6]: 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 [7]: f.factors()
Out[7]: 
([Poly(x^3 + 2x + 1, GF(3)),
  Poly(x^4 + x + 2, GF(3)),
  Poly(x^5 + 2x + 1, GF(3))],
 [5, 4, 3])