Factoring Strategies

note

This is Lab 8 from Clint by Hugh Montgomery, edited by Codex and Elad Zelingher. All rights reserved to Hugh Montgomery.

We know that trial division yields a rigorous proof of the factorization of $n$ in at most $O(\sqrt n)$ steps. This is slow when $n$ is large, so we now consider methods that are faster for large $n$. Our object here is not to present state-of-the-art factoring, but only to drive home the point that it is possible to construct factoring strategies that are much faster than trial division.

Problem 1

Trial division takes $\approx \sqrt n$ steps if $n$ is prime or if $n$ is the product of two primes, $n=p_1p_2$ with $p_1\approx p_2\approx \sqrt n$. However these are the worst cases, and trial division is much quicker for many numbers. To see why this is so, suppose that $n$ is composite and that $p_1<p_2<\ldots<p_k$ are the distinct primes dividing $n$. Explain why only $O(\log n)+O(p_{k-1})+O(\sqrt{p_k})$ trial divisions are required to factor $n$. Trial division is unlikely to yield the complete factorization of a large $n$ in a reasonable amount of time, but nevertheless one should always try divisors through 100000 or so, when asked to factor a number $n$ of unknown multiplicative structure.

Problem 2

Although alternative factoring strategies can be traced as far back as Fermat and Gauss, we begin with a simple method of comparatively recent origin, namely Pollard's Rho Method, proposed in 1975 by J. M. Pollard. (Why it should be called “Rho” is explained on p. 81 of NZM.) Suppose that a prime number $p$ has been chosen. Let $u_0=1$, and for $i>0$ let the numbers $u_i$ be determined by the relations $u_i\equiv u_{i-1}^2+c\pmod p$, $0\leq u_i<p$. Here $c$ is some constant. We usually start with $c=1$, but other values of $c$ are sometimes handy, as will become clear later. The sequence $u_i$ may have a non-periodic initial segment, but once a value is repeated (as must eventually happen), the sequence becomes periodic. The program RhoDem will assist you in determining when this first repetition occurs. Use RhoDem, and in response to the query “Use cycle-detecting algorithm?” respond by selecting “List the sequence only.” Enter $p=89$, and set $c=1$. In the sequence of $u_i$ displayed, you will see that $u_2=u_{16}=2$, but that $u_1\ne u_{15}$. Thus the first repeat is at $u_{16}$, and the period of the repetitions is 14. In general, let $r(p)$ be the least index $i$ such that the value $u_i$ repeats a value found previously, and let $l(p)$ denote the least period of the repetitions. Thus $r(89)=16$ and $l(89)=14$. Repeat this calculation for the prime $p=29$, and thus determine the values of $r(29)$ and $l(29)$.

By the pigeon-hole principle we see that $r(p)\leq p+1$, but the “Birthday Paradox” leads us to expect that $r(p)\approx \sqrt p$ for most primes, and for most choices of $c$. (See Lemma 2.21 in NZM, and the discussion following.)

Problem 3

In the examples above it is easy to spot the first repetition visually, but this task becomes rapidly more difficult when $p$ is a little larger. Repeat the steps above with $p=3463$. Scroll down through the table, and as you go, note the following four values:

$i$	$u(i)$
130	2185
131	2212
$\vdots$	$\vdots$
147	1278
148	2212

Thus $r(3463)=147$ and $l(3463)=17$. Since it is quite tedious (and time-consuming!) to compare each value with all the previous ones, we need a quick way to spot repetitions. This is provided by the following Cycle Detection Algorithm: Watch for an index $i$ at which $u_i=u_{2i}$. Let $s(p)$ denote the least such $i$. The advantages of this approach are that only one comparison need be made, and that only the values $u_i$ and $u_{2i}$. Thus we have no need to store the values of the $u_i$. If $u_i\ne u_{2i}$ then we use the recurrence once to compute $u_{i+1}$, and twice more to compute $u_{2i+2}$. The old values $u_i$, $u_{2i}$ are discarded, and we continue with the two new values. The disadvantage of this approach is that it is slightly inefficient, in the sense that the recurrence must be used $3s(p)$ times, which is somewhat larger than $r(p)$, which would be optimal. Using RhoDem, complete the following table (the first row of which has been thoughtfully provided). Use RhoDem with no cycle-detecting first, to determine the values of $r(p)$ and $l(p)$. By inspecting the values $u_i$, try to determine the value of $s(p)$. Check your work by applying RhoDem a second time with cycle-detecting.

$p$	$r$	$s$	$l$
37	6	5	1
41
43
47
53

Problem 4

When we apply the Rho method to factor a number $m$, we compute the sequence $u_i$ modulo $m$. Suppose that $p\mid m$. We can't construct the sequence $u_i$ (mod $p$), because the prime $p$ is unknown. However, the $u_i$ computed are congruent (mod $p$) to those we would have obtained if we had worked (mod $p$) (recall Theorem 2.1(5) of NZM). Hence $u_i\equiv u_{2i}\pmod p$ when $i=s(p)$. Let $s_0(m)$ denote the least index $i$ such that $(u_i-u_{2i},m)>1$. Then

$$s_0(m)=\min_{p\mid m}s(p).$$

Moreover, for this index $i$ we have $(u_i-u_{2i},m)<m$ unless $s(p)=s_0(m)$ for all $p\mid m$. Take $m=p_1p_2$ where the $p_i$ are selected from the above table in such a way that $s(p_1)\ne s(p_2)$. Apply RhoDem to this $m$, with cycle-detecting, and note the point at which a divisor is found. Repeat this, with the $p_i$ selected so that $s(p_1)=s(p_2)$. Note that the gcd jumps from 1 to $m$, but that RhoDem does not give up. What does RhoDem do, instead? Finally, choose two $p_i$ so that $p_1<p_2$ but $r(p_1)>r(p_2)$, and note that the prime factor found by RhoDem is not the least prime factor of $m$.

warning

The Pollard Rho Method should only be applied to numbers that are already known to be composite (as the result of a strong pseudoprime test, for example). If it were applied to a large prime number $p$, it would run endlessly, switching to ever larger values of $c$.

Problem 5

Apply RhoDem to $m=11111111111111111=(10^{17}-1)/9$. What is the least $s$ for which $(u_{2s}-u_s,m)>1$? The program Rho will attempt to factor a given number $m$ by means of the Pollard rho algorithm. Apply Rho to 11111111111111111. Is this much faster than using the program Factor? What do you expect the running time of Rho to be, on average, as a function of the size of the least prime factor of $m$?

Problem 6

What inequalities can be established between the three quantities $r(p)$, $s(p)$, $l(p)$? Explore.

Problem 7

In general you should avoid taking $c=0$ or $c=-2$ in the rho method. Experiment with these values of $c$, using RhoDem, and try to explain why these values of $c$ are bad. (Hint: For $c=-2$, note that if $x\cdot\overline{x}\equiv 1\pmod p$ and $u\equiv x-\overline{x}\pmod p$ then $u^2-2\equiv x^2-\overline{x}^2\pmod p$.)

Problem 8

For the programmer. Richard Brent has observed that the cycle-detecting algorithm can be made about 24% more efficient, as follows: Suppose that you have calculated $u_n$ and $u_{2n}$, and that you have tried $(u_j-u_k,m)$ for pairs $(j,k)$ with the difference $j-k$ running from $1$ to $n$. Starting from $u_{2n}$, apply the iteration $n+1$ times, to evaluate $u_{3n+1}$. Next compute $(u_{3n+1}-u_{2n},m)$, $(u_{3n+2}-u_{2n},m)$, $\dots$, $(u_{4n}-u_{2n},m)$. Here the differences between the subscripts range from $2n+1$ to $4n$. If you start this with $n=1$, then $n$ runs through powers of $2$. To speed things up further, do not calculate the gcd separately for each term indicated above. Instead, form a product of these numbers, keeping track of the number of factors in the product. When the number of factors reaches $8$, compute the gcd of the product with $m$. The product, like everything else, is computed modulo $m$.

Problem 9

We now turn to a second method proposed by Pollard, the “$p-1$ Method.” Suppose that $m$ is a number to be factored, that $p\mid m$, and that $(p-1)\mid k!$, so that $a^{k!}\equiv 1\pmod p$ whenever $(a,m)=1$, which is to say that $p\mid(a^{k!}-1,m)$. Thus we use the powering algorithm to calculate a number $x$, $0\leq x<m$, so that $x\equiv a^{k!}\pmod m$, and then we use the Euclidean algorithm to evaluate $(x-1,m)$ in the hope that this will disclose a proper factor of $m$. If this gcd is still 1 then we try a larger $k$; if it is $m$ then we switch to a different value of $a$. This method is rather erratic: It is remarkably fast for some numbers, but for other numbers it is no faster than trial division. Apply the program P–1Dem to several numbers, and note how the calculation proceeds. The program P–1 is ridiculously fast when applied to $m=99999997425160993$. Use P–1 to break $m$ into factors, use Factor to verify that the factors are indeed prime, say $m=p\cdot p'$. Apply Factor to $p-1$ and to $p'-1$, and thus demonstrate why P–1 is so quick for this number. At the opposite extreme, the program P–1 will take an uncomfortably long time to factor the comparatively small number $m=9904156957$. Find the prime factors $p$ of this $m$, and also the factorization of $p-1$ for each such $p$, to explain why the method is so slow in this case. Finally, apply the program P–1 to our old favorite, $m=11111111111111111=(10^{17}-1)/9$.

Problem 10

For the programmer. The Pollard $p-1$ method, as explained above, is slightly inefficient because the power of 2 dividing $k!$ is much larger than is likely to be needed. Try using $d_k$ instead of $k!$, where $d_k$ denotes the least common multiple of the integers $1,2,\dots,k$. Show that $d_k=a_1\cdot a_2\cdot\dots\cdot a_k$ where $a_n=p$ if $n$ is a power of $p$, $a_n=1$ otherwise. Note that $d_k=d_{k-1}$ unless $k$ is a primepower. Thus it is necessary to compute $(a^{d_k}-1,m)$ only when $k$ is a primepower. Does this lead to a more efficient method?

It is notable that we have no proof that the Pollard Rho Method is efficient, although we believe that on average it will yield a proper divisor of $n$ in $O(\sqrt p)$ steps, where $p$ is the smallest prime factor of $n$. Although the $p-1$ method is erratic, the idea behind the method is used in other methods, notably the Elliptic Curve Method (ECM), devised by Lenstra in 1987. (See §5.8 of NZM.) In 1982, Carl Pomerance invented the Quadratic Sieve method (QS) of factoring, which has been further developed to become the Multiple Polynomial Quadratic Sieve (MPQS). These methods have largely usurped an older method, CFRAC, based on properties of continued fractions. A new method, the Number Field Sieve, (NFS) is currently being developed, and has already achieved some notable successes.

For more information concerning factoring, consult the following sources.

• D. M. Bressoud, Factorization and primality testing, Springer-Verlag, New York, 1989.
• D. V. Chudnovsky and G. V. Chudnovsky, “Sequences of numbers generated by addition in formal groups and new primality and factorization tests,” Adv. Appl. Math. 7 (1986), 385–434.
• D. Coppersmith, “Modifications to the number field sieve,” J. Cryptology 6 (1993), 169–180.
• J. D. Dixon, “Factorization and primality tests,” Amer. Math. Monthly 91 (1984), 333–352.
• R. K. Guy, “How to factor a number,” Proc. Fifth Conf. Numerical Math., Utilitas, Winnipeg, 1975, pp. 49–89.
• P. L. Montgomery, “Speeding the Pollard and elliptic methods of factorization,” Math. Comp. 48 (1987), 243–264.
• C. Pomerance, Lecture Notes on Primality Testing and Factoring, MAA Notes 4, Math. Assoc. of America, Washington, 1984.
• H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhäuser, Boston, 1985, 464 pp.
• H. C. Williams, “Factoring on a computer,” Math. Intell. 6 (1984), 29–36.
• M. C. Wunderlich, “Computational methods for factoring large integers,” Abacus 5 (1988), 19–33.