galois.factors(value: int) → tuple[list[int], list[int]]
galois.factors(value: Poly) → tuple[list[galois._polys._poly.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\}\).

Notes

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], [1]. 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().

References

Examples

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])

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])