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

list – Sorted list of prime factors \(p = [p_1, p_2, \dots, p_{n-1}]\) with \(p_1 < p_2 < \dots < p_{n-1}\).
list – List 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]: ([2, 3, 5], [3, 1, 1])

# The product of the prime powers is the factored integer
In [3]: np.multiply.reduce(np.array(p) ** np.array(k))
Out[3]: 120

Prime factorization of 1 less than a large prime.

In [4]: prime =1000000000000000035000061

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

In [6]: p, k = galois.prime_factors(prime - 1)

In [7]: p, k
Out[7]: ([2, 3, 5, 17, 19, 51599587203302375387], [2, 1, 1, 1, 1, 1])

In [8]: np.multiply.reduce(np.array(p) ** np.array(k))
Out[8]: 1000000000000000035000060