galois.factors¶

galois.factors(value: int) → tuple[list[int], list[int]]¶

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

Computes the prime factors of a positive integer or the irreducible factors of a non-constant, monic polynomial.

Parameters

value: int¶

value: Poly

A positive integer \(n\) or a non-constant, monic polynomial \(f(x)\).

Returns

• Sorted list of prime factors \(\{p_1, p_2, \dots, p_k\}\) of \(n\) with \(p_1 < p_2 < \dots < p_k\) or 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\}\).

Notes

Integers

This function factors a positive integer \(n\) into its \(k\) prime factors such that \(n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}\).

Steps:

1. Test if \(n\) is prime. If so, return [n], [1].

2. Test if \(n\) is a perfect power, such that \(n = x^k\). If so, prime factor \(x\) and multiply the exponents by \(k\).

3. Use trial division with a list of primes up to \(10^6\). If no residual factors, return the discovered prime factors.

4. Use Pollard’s Rho algorithm to find a non-trivial factor of the residual. Continue until all are found.

Polynomials

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.

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

3. Apply the Equal-Degree Factorization algorithm to factor the product of factors of equal degree into their irreducible 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

Integers

Construct a composite integer from prime factors.

In [1]: n = 2**3 * 3 * 5; n
Out[1]: 120

Factor the integer into its prime factors.

In [2]: galois.factors(n)
Out[2]: ([2, 3, 5], [3, 1, 1])

Polynomials

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

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

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

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

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

Construct a composite polynomial.

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

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