Factoring II

In continuation of my previous post on factoring, I continue to explore these methods. From Pollard’s $latex \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 $latex \mathrm {gcd} (a,n) = 1$, i.e. if a and n are relatively prime, then $latex a^{\phi (n)} \equiv 1 \mod n$, where $latex \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 $latex \mathrm {gcd} (a,p) = 1$, with p a prime, then $latex 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 $latex 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 $latex 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 $latex \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 $latex a^{p-1} \equiv 1 \mod p$. Since p-1 is B-power smooth, we know that $latex (p-1) | m = \mathrm{lcm} (1, 2, …, B)$. Thus $latex a^m \equiv 1 \mod p$, or rather $latex p | (a^m – 1)$.

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

This entry was posted in Expository, Math.NT, Mathematics and tagged , , , , , , . Bookmark the permalink.

One Response to Factoring II

  1. Pingback: Factoring III « mixedmath

Leave a Reply