galois.prime_factors¶
- class galois.prime_factors(n)¶
Computes the prime factors of the positive integer \(n\).
The integer \(n\) can be factored into \(n = p_1^{e_1} p_2^{e_2} \dots p_{k-1}^{e_{k-1}}\).
Steps:
Test if \(n\) is prime. If so, return
[n], [1]
.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.
- Parameters
n (int) – The positive integer to be factored.
- Returns
list – Sorted list of \(k\) prime factors \(p = [p_1, p_2, \dots, p_{k-1}]\) with \(p_1 < p_2 < \dots < p_{k-1}\).
list – List of corresponding prime powers \(e = [e_1, e_2, \dots, e_{k-1}]\).
Examples
In [610]: p, e = galois.prime_factors(120) In [611]: p, e Out[611]: ([2, 3, 5], [3, 1, 1]) # The product of the prime powers is the factored integer In [612]: np.multiply.reduce(np.array(p) ** np.array(e)) Out[612]: 120
Prime factorization of 1 less than a large prime.
In [613]: prime =1000000000000000035000061 In [614]: galois.is_prime(prime) Out[614]: True In [615]: p, e = galois.prime_factors(prime - 1) In [616]: p, e Out[616]: ([2, 3, 5, 17, 19, 112850813, 457237177399], [2, 1, 1, 1, 1, 1, 1]) In [617]: np.multiply.reduce(np.array(p) ** np.array(e)) Out[617]: 2003764205241896700