mixedmath

In continuation of my previous post on factoring, I continue to explore these methods. From Pollard's $\rho$ 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 $\mathrm {gcd} (a,n) = 1$, i.e. if a and n are relatively prime, then $a^{\phi (n)} \equiv 1 \mod n$, where $\phi (n)$ 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 $\mathrm {gcd} (a,p) = 1$, with p a prime, then $ a^{p-1} \equiv 1 \mod p$.

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 $24 = 2^3 \cdot 3$ is 3-smooth (and 4-smooth, 5-smooth, etc). We call a number B-power smooth if all prime powers $p_i ^{n_i}$ 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 $\mathrm{lcm} (1, 2, 3, ..., B)$.

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 $a^{p-1} \equiv 1 \mod p$. Since p-1 is B-power smooth, we know that $(p-1) | m = \mathrm{lcm} (1, 2, ..., B)$. Thus $a^m \equiv 1 \mod p$, or rather $p | (a^m - 1)$.

Thus $p| \mathrm{gcd} (a^m - 1, N) > 1$. 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 $10^6$)
2. Compute $m = \mathrm{lcm} (1, 2, ..., B)$
3. Set a = 2.
4. Compute $x = a^m - 1 \mod N$ and $g = \mathrm{gcd} (x, N)$
5. If we've found a nontrivial factor, then that's grand. If not, and if $a < 20$ (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 $O(B \; log_2 B)$ complexity (using the Sieve of Erosthanes, for example). The modular exponentiation will take $O( \; (log_2 N)^2)$ time. Calculating the gcd takes only $O( \; (log_2 N)^3)$, so the overall algorithm takes $O(B \cdot lob_2 B \cdot (log_2 N)^2 + (log_2 N)^3)$ 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 $\dfrac{1}{27}$ 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 $B = 10^6$ 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.

Leave a comment

Comment via email