galois.factors¶
- galois.factors(value)¶
Computes the prime factors of a positive integer or the irreducible factors of a non-constant, monic polynomial.
- Parameters
value (int, galois.Poly) – A positive integer \(n\) or a non-constant, monic polynomial \(f(x)\).
- Returns
list – 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 – List of corresponding multiplicities \(\{e_1, e_2, \dots, e_k\}\).
Notes
Integer Factorization
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 prime. If so, return
[n], [1]
.Test if \(n\) is a perfect power, such that \(n = x^k\). If so, prime factor \(x\) and multiply the exponents by \(k\).
Use trial division with a list of primes up to \(10^6\). If no residual factors, return the discovered prime factors.
Use Pollard’s Rho algorithm to find a non-trivial factor of the residual. Continue until all are found.
Polynomial Factorization
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.
Apply the Distinct-Degree Factorization algorithm to factor each square-free polynomial into a product of factors with the same degree.
Apply the Equal-Degree Factorization algorithm to factor the product of factors of equal degree into their irreducible factors.
References
Hachenberger, D. Jungnickel. Topics in Galois Fields. Algorithm 6.1.7.
Section 2.1 from https://people.csail.mit.edu/dmoshkov/courses/codes/poly-factorization.pdf
Examples
Factor a positive integer.
In [1]: galois.factors(120) Out[1]: ([2, 3, 5], [3, 1, 1])
Factor a polynomial over \(\mathrm{GF}(3)\).
In [2]: GF = galois.GF(3) In [3]: g1, g2, g3 = galois.irreducible_poly(3, 3), galois.irreducible_poly(3, 4), galois.irreducible_poly(3, 5) In [4]: g1, g2, g3 Out[4]: (Poly(x^3 + 2x + 1, GF(3)), Poly(x^4 + x + 2, GF(3)), Poly(x^5 + 2x + 1, GF(3))) In [5]: e1, e2, e3 = 5, 4, 3 # Construct the composite polynomial In [6]: f = g1**e1 * g2**e2 * g3**e3 In [7]: galois.factors(f) 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])