galois.prime_factors¶
-
galois.
prime_factors
(x)[source]¶ Computes the prime factors of the positive integer \(x\).
The integer \(x\) can be factored into \(x = p_1^{k_1} p_2^{k_2} \dots p_{n-1}^{k_{n-1}}\).
- Parameters
x (int) – The positive integer to be factored.
- Returns
numpy.ndarray – Sorted array of prime factors \(p = [p_1, p_2, \dots, p_{n-1}]\) with \(p_1 < p_2 < \dots < p_{n-1}\).
numpy.ndarray – Array of corresponding prime powers \(k = [k_1, k_2, \dots, k_{n-1}]\).
Examples
In [1]: p, k = galois.prime_factors(120) In [2]: p, k Out[2]: (array([2, 3, 5]), array([3, 1, 1])) # The product of the prime powers is the factored integer In [3]: np.multiply.reduce(p ** k) Out[3]: 120 # Prime factorization of 1 less than a large prime In [4]: p, k = galois.prime_factors(1000000000000000035000061 - 1) In [5]: p, k Out[5]: (array([2, 3, 5, 17, 19, 51599587203302375387], dtype=object), array([2, 1, 1, 1, 1, 1])) In [6]: np.multiply.reduce(p ** k) Out[6]: 1000000000000000035000060