galois.factors

galois.factors(n)

Computes the prime factors of the positive integer \(n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}\).

Parameters

n (int) – Any positive integer.

Returns

  • list – Sorted list of \(k\) prime factors \(\{p_1, p_2, \dots, p_k\}\) with \(p_1 < p_2 < \dots < p_k\).

  • list – List of corresponding prime powers \(\{e_1, e_2, \dots, e_k\}\).

Notes

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.

Examples

In [1]: p, e = galois.factors(120)

In [2]: p, e
Out[2]: ([2, 3, 5], [3, 1, 1])

In [3]: galois.prod([pi**ei for pi, ei in zip(p, e)])
Out[3]: 120

Prime factorization of one less than a large prime.

In [4]: prime = 1000000000000000035000061

In [5]: galois.is_prime(prime)
Out[5]: True

In [6]: p, e = galois.factors(prime - 1)

In [7]: p, e
Out[7]: ([2, 3, 5, 17, 19, 112850813, 457237177399], [2, 1, 1, 1, 1, 1, 1])

In [8]: galois.prod([pi**ei for pi, ei in zip(p, e)])
Out[8]: 1000000000000000035000060