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:

  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.

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:

  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

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