- 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:¶
- 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:
Test if \(n\) is in the Cunningham Book’s database of \(n = p^m \pm 1\) factorizations. If so, return the prime factorization.
Test if \(n\) is prime. If so, return
[n], [1]
. Seeis_prime()
.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()
.Use trial division with a list of primes up to \(10^6\). If no residual factors, return the discovered prime factors. See
trial_division()
.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:
Apply the Square-Free Factorization algorithm to factor the monic polynomial into square-free polynomials. See
Poly.square_free_factors()
.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()
.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¶
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¶
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])