Number Theory

Prime Factorization in Python: Part 2

Learn how to use the Pollard’s Rho Algorithm!

In the first part of this two-article series on prime factorization, I talked about using the simple method of the Sieve of Eratosthenes to factor a number. At the end of that article, I hinted on a much more efficient (but more complicated as well) method: Pollard’s Rho Algorithm.

In case you haven’t read Part 1, you can access it here:

Prime Factorization in Python: Part 1

The Approach: Pollard’s Rho

Last time, we talked about using the Sieve of Eratosthenes to find a list of primes, then use that list of primes to factor a number. However, we can use Pollard’s Rho Algorithm to directly factor a number into its primes.

Pollard’s Rho Algorithm takes the form of 2 parts:

1. A polynomial, g(x) = (x ** 2 - 1) % n
2. Values n , the number to be factorized; x , starting at 2; and y , a random integer less than n