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 lexicographical order.

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

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 in the Cunningham Book’s database of $$n = p^m \pm 1$$ factorizations. If so, return the prime factorization.

2. Test if $$n$$ is prime. If so, return [n], . See is_prime().

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

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

5. Use Pollard’s Rho algorithm to find a non-trivial factor of the residual. Continue until all are found. See pollard_rho().

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

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

This factorization is also available in Poly.factors().

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

Examples

Construct a composite integer from prime factors.

In : n = 2**3 * 3 * 5; n
Out: 120


Factor the integer into its prime factors.

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


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 : galois.factors(f)
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])