mixedmath

Explorations in math and programming
David Lowry-Duda



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

Info on how to comment

To make a comment, please send an email using the button below. Your email address won't be shared (unless you include it in the body of your comment). If you don't want your real name to be used next to your comment, please specify the name you would like to use. If you want your name to link to a particular url, include that as well.

bold, italics, and plain text are allowed in comments. A reasonable subset of markdown is supported, including lists, links, and fenced code blocks. In addition, math can be formatted using $(inline math)$ or $$(your display equation)$$.

Please use plaintext email when commenting. See Plaintext Email and Comments on this site for more. Note also that comments are expected to be open, considerate, and respectful.

Comment via email

Comments (1)
  1. 2011-07-26 davidlowryduda, in a followup post

    [...] 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 [...]