In continuation of my previous post on factoring, I continue to explore these methods. From Pollard’s method, we now consider Pollard’s p-1 algorithm.

Before we consider the algorithm proper, let’s consider some base concepts.

Firstly, I restate Euler’s Theorem (of course, Euler was prolific, and so there are altogether too many things called Euler’s Theorem – but so it goes):

If , i.e. if a and n are relatively prime, then , where is the Euler Totient Function or Euler’s Phi Function (perhaps as opposed to someone else’s phi function?). As a corollary, we get Fermat’s Little Theorem, which says that if , with p a prime, then .

The second base concept is called smoothness. A number is called B-smooth is none of its prime factors is greater than B. A very natural question might be: why do we always use the letter B? I have no idea. Another good question might be, what’s an example? Well, the number is 3-smooth (and 4-smooth, 5-smooth, etc). We call a number B-power smooth if all prime powers dividing the number are less than or equal to B. So 24 is 8-power smooth, but not 7-power smooth. Note also that in this case, the number is a factor of .

Pollard’s (p-1) algorithm is called the “p-1” algorithm because it is a specialty factorization algorithm. Suppose that we are trying to factorize a number N and we choose a positive integer B, and that there is a prime divisor p of N such that p-1 is B-power smooth (we choose B beforehand – it can’t be too big or the algorithm becomes computationally intractable). Now for a positive integer a coprime to p, we get . Since p-1 is B-power smooth, we know that . Thus , or rather .

Thus . And so one hopes that this factor is nontrivial and proper.

This is the key idea behind the entire algorithm.

Pollard’s (p-1) Algorithm

1. Choose a smoothness bound B (often something like )

2. Compute

3. Set a = 2.

4. Compute and

5. If we’ve found a nontrivial factor, then that’s grand. If not, and if (say), then replace a by a+1 and go back to step 4.

So how fast is the algorithm? Well, computing the lcm will likely take something in the order of complexity (using the Sieve of Erosthanes, for example). The modular exponentiation will take time. Calculating the gcd takes only , so the overall algorithm takes or so. In other words, it’s only efficient is B is small; but when B is small, fewer primes can be found.

I’ve read that Dixon’s Theorem guarantees that there is a probability of about that a value of B the size of $N^{1/6}$ will yield a factorization. Unfortunately, this grows untenably large. In practice, this algorithm is an excellent way to eliminate the possibility of small factors (or to successfully divide out small factors). Using will identify smaller factors and allows different techniques, such as the elliptic curve factorization algorithm, to try to find larger factors.

I’ll expand on more factoring later.

[…] is a continuation of my last factoring post. I thought that I might have been getting ahead of myself, as I left out a relatively simple idea […]