# 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], .

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

1. Hachenberger, D. Jungnickel. Topics in Galois Fields. Algorithm 6.1.7.

Examples

Factor a positive integer.

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


Factor a polynomial over $$\mathrm{GF}(3)$$.

In : GF = galois.GF(3)

In : g1, g2, g3 = galois.irreducible_poly(3, 3), galois.irreducible_poly(3, 4), galois.irreducible_poly(3, 5)

In : g1, g2, g3
Out:
(Poly(x^3 + 2x + 1, GF(3)),
Poly(x^4 + x + 2, GF(3)),
Poly(x^5 + 2x + 1, GF(3)))

In : e1, e2, e3 = 5, 4, 3

# Construct the composite polynomial
In : f = g1**e1 * g2**e2 * g3**e3

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