Reference / Paper · 1996
A Tale of Two Sieves (Notices of the AMS 43(12), 1473–1485)
Readable history of the quadratic sieve and the number field sieve.
Reference / Paper · 1996
Readable history of the quadratic sieve and the number field sieve.
pomerance.qxp 5/7/98 9:16 AM Page 1473 A Tale of Two Sieves Carl Pomerance (This paper is dedicated to the memory of my friend and teacher, Paul Erdos) I t is the best of times for the game of factoring large numbers into their prime factors. In 1970 it was barely possible to factor “hard” 20-digit numbers. In 1980, in the heyday of the Brillhart-Morrison continued fraction factoring algorithm, factoring of 50-digit numbers was becoming commonplace. In 1990 my own quadratic sieve factoring algorithm had doubled the length of the numbers that could be factored, the record having 116 digits. By 1994 the quadratic sieve had factored the famous 129-digit RSA challenge number that had been estimated in Martin Gardner’s 1976 Scientific American column to be safe for 40 quadrillion years (though other estimates around then were more modest). But the quadratic sieve is no longer the champion. It was replaced by Pollard’s number field sieve in the spring of 1996, when that method successfully split a 130-digit RSA challenge number in about 15% of the time the quadratic sieve would have taken. In this article we shall briefly meet these factorization algorithms—these two sieves—and some of the many people who helped to develop them. In the middle part of this century, computational issues seemed to be out of fashion. In most books the problem of factoring big numbers Carl Pomerance is research professor of mathematics at the University of Georgia, Athens, GA. His e-mail address is [email protected]. Supported in part by National Science Foundation grant number DMS-9206784. DECEMBER 1996 was largely ignored, since it was considered trivial. After all, it was doable in principle, so what else was there to discuss? A few researchers ignored the fashions of the time and continued to try to find fast ways to factor. To these few it was a basic and fundamental problem, one that should not be shunted to the side. But times change. In the last few decades we have seen the advent of accessible and fast computing power, and we have seen the rise of cryptographic systems that base their security on our supposed inability to factor quickly (and on other number theoretic problems). Today there are many people interested in factoring, recognizing it not only as a benchmark for the security of cryptographic systems, but for computing itself. In 1984 the Association for Computing Machinery presented a plaque to the Institute for Electrical and Electronics Engineers (IEEE) on the occasion of the IEEE centennial. It was inscribed with the prime factorization of the number 2251 − 1 that was completed that year with the quadratic sieve. The president of the ACM made the following remarks: About 300 years ago the French mathematician Mersenne speculated that 2251 − 1 was a composite, that is, a factorable number. About 100 years ago it was proved to be factorable, but even 20 years ago the computational load to factor the number was considered insurmountable. Indeed, using conventional machines and traditional search algorithms, the search time NOTICES OF THE AMS 1473 pomerance.qxp 5/7/98 9:16 AM Page 1474 was estimated to be about 1020 years. The number was factored in February of this year at Sandia on a Cray computer in 32 hours, a world record. We’ve come a long way in computing, and to commemorate IEEE’s contribution to computing we have inscribed the five factors of the Mersenne composite on a plaque. Happy Birthday, IEEE. Factoring big numbers is a strange kind of mathematics that closely resembles the experimental sciences, where nature has the last and definitive word. If some method to factor n runs for awhile and ends with the statement “ d is a factor of n”, then this assertion may be easily checked; that is, the integers have the last and definitive word. One can thus get by quite nicely without proving a theorem that a method works in general. But, as with the experimental sciences, both rigorous and heuristic analyses can be valuable in understanding the subject and moving it forward. And, as with the experimental sciences, there is sometimes a tension between pure and applied practitioners. It is held by some that the theoretical study of factoring is a freeloader at the table (or as Hendrik Lenstra once colorfully put it, paraphrasing Siegel, “a pig in the rose garden”), enjoying undeserved attention by vapidly giving various algorithms labels, be they “polynomial”, “exponential”, “random”, etc., and offering little or nothing in return to those hard workers who would seriously compute. There is an element of truth to this view. But as we shall see, theory played a significant role in the development of the title’s two sieves. A Contest Problem But let us begin at the beginning, at least my beginning. When I give talks on factoring, I often repeat an incident that happened to me long ago in high school. I was involved in a math contest, and one of the problems was to factor the number 8051. A time limit of five minutes was given. It is not that we were not allowed to use pocket calculators; they did not exist in 1960, around when this event occurred! Well, I was fairly good at arithmetic, and I was sure I could trial divide up to the square root of 8051 (about 90) in the time allowed. But on any test, especially a contest, many students try to get into the mind of the person who made it up. Surely they would not give a problem where the only reasonable approach was to try possible divisors frantically until one was found. There must be a clever alternate route to the answer. So I spent a couple of minutes looking for the clever way, but grew worried that I was wasting too much time. I then belatedly started trial division, but 1474 NOTICES OF THE AMS I had wasted too much time, and I missed the problem. So can you find the clever way? If you wish to think about this for a moment, delay reading the next paragraph. Fermat and Kraitchik The trick is to write 8051 as 8100 − 49, which is 902 − 72 , so we may use algebra, namely, factoring a difference of squares, to factor 8051. It is 83 × 97 . Does this always work? In fact, every odd composite can be factored as a difference of 2 1 squares: just 2 use the identity ab = 2 (a + b) − 12 (a − b) . Trying to find a pair of squares which work is, in fact, a factorization method of Fermat. Just like trial division, which has some very easy cases (such as when there is a small prime factor), so too does the difference-ofsquares method have easy cases. For example, √ if n = ab where a and b are very close to n , as in the case of n = 8051 , it is easy to find the two squares. But in its worst cases, the difference-of-squares method can be far worse than trial division. It is worse in another way too. With trial division, most numbers fall into the easy case; namely, most numbers have a small factor. But with the difference-of-squares method, only a small fraction of numbers have a divisor near their square root, so the method works well on only a small fraction of possible inputs. (Though trial division allows one to begin a factorization for most inputs, finishing with a complete factorization is usually far more difficult. Most numbers resist this, even when a combination of trial division and difference-ofsquares is used.) In the 1920s Maurice Kraitchik came up with an interesting enhancement of Fermat’s difference-of-squares technique, and it is this enhancement that is at the basis of most modern factoring algorithms. (The idea had roots in the work of Gauss and Seelhoff, but it was Kraitchik who brought it out of the shadows, introducing it to a new generation in a new century. For more on the early history of factoring, see [23].) Instead of trying to find integers u and v with u2 − v 2 equal to n, Kraitchik reasoned that it might suffice to find u and v with u2 − v 2 equal to a multiple of n, that is, u2 ≡ v 2 mod n . Such a congruence can have uninteresting solutions, those where u ≡ ±v mod n, and interesting solutions, where u 6≡ ±v mod n. In fact, if n is odd and divisible by at least two different primes, then at least half of the solutions to u2 ≡ v 2 mod n , with uv coprime to n, are of the interesting variety. And for an interesting solution u, v , the greatest common factor of u − v and n, denoted (u − v, n), must be a nontrivial factor of n . Indeed, n divides u2 − v 2 = VOLUME 43, NUMBER 12 pomerance.qxp 5/7/98 9:16 AM Page 1475 (u − v)(u + v) but divides neither factor. So n must be somehow split between u − v and u + v. As an aside, it should be remarked that finding the greatest common divisor (a, b) of two given numbers a and b is a very easy task. If 0 < a ≤ b and if a divides b , then (a, b) = a . If a does not divide b , with b leaving a remainder r when divided by a, then (a, b) = (a, r ) . This neat idea of replacing a larger problem with a smaller one is over two thousand years old and is due to Euclid. It is very fast: it takes about as much time for a computer to find the greatest common divisor of a and b as it would take to multiply them together. Let us see how Kraitchik might have factored n = 2041 . The first square above n is 462 = 2116 . Consider the sequence of numbers Q(x) = x2 − n for x = 46, 47, . . . . We get 75, 168, 263, 360, 459, 560, . . . . So far no squares have appeared, so Fermat might still be searching. But Kraitchik has another option: namely, he tries to find several numbers x with the product of the corresponding numbers Q(x) equal to a square. For if Q(x1 ) · · · Q(xk ) = v 2 and x1 · · · xk = u , then u2 = x21 · · · x2k ≡ (x21 − n) · · · (x2k − n) = Q(x1 ) · · · Q(xk ) = v 2 mod n; that is, we have found a solution to u2 ≡ v 2 mod n . But how to find the set x1 , . . . , xk ? Kraitchik notices that some of the numbers Q(x) factor very easily: Lehmer and R. E. Powers suggested replacing Kraitchik’s function Q(x) = x2 − n with another that is derived from the continued-fraction ex√ pansion of n . If ai /bi is the i-th continued fraction con√ n , let Qi = ai2 − bi2 n . Then vergent to 2 Qi ≡ ai mod n. Thus, instead of playing with the numbers Q(x) , we may play with the numbers Qi , since in both cases they are congruent modulo n to known squares. Although continued fractions can be ornery beasts as far as computation goes, the case for quadratic irrationals is quite pleasant. In fact, there is a simple iterative procedure (see [16]) going back to Gauss and perhaps earlier for computing what is needed here, namely, the sequence of integers Qi and the residues ai mod n. But why mess up a perfectly simple quadratic polynomial with something as exotic as continued fractions? It is because of the inequality √ |Qi | < 2 n. The numbers Qi are smaller in absolute value than the numbers Q(x) . (As x moves √ away from n , the numbers Q(x) grow ap√ proximately linearly, with a slope of 2 n .) If one wishes to “play” with numbers to find some of them with product a square, it is presumably easier to do this with smaller numbers than with larger numbers. So the continued fraction of Lehmer and Powers has an apparent advantage over the quadratic polynomial of Kraitchik. How to “Play” with Numbers The essence of Kraitchik’s method is to “play” with the sequence x2 − n as x runs through in√ tegers near n to find a subsequence with product a square. If the square root of this square is v and the product of the corresponding x values is u, then u2 ≡ v 2 mod n , and there is now a hope that this congruence is “interesting”, namely, that u 6≡ ±v mod n . In 1931 D. H. It is certainly odd to have an instruction in an algorithm asking you to play with some numbers to find a subset with product a square. I am reminded of the cartoon with two white-coated scientists standing at a blackboard filled with arcane notation, and one points to a particularly delicate juncture and says to the other that at this point a miracle occurs. Is it a miracle that we were able to find the numbers 75, 168, 360, and 560 in Kraitchik’s sequence with product a square? Why should we expect to find such a subsequence, and, if it exists, how can we find it efficiently? A systematic strategy for finding a subsequence of a given sequence with product a square was found by John Brillhart and Michael Morrison, and, surprisingly, it is at heart only linear algebra (see [16]). Every positive integer m has an exponent vector v(m) that is based on the prime factorization of Q mv. Let pi denote the i-th prime, and say m = pi i . (The product is over all primes, but only finitely many of the exponents vi are nonzero.) Then v(m) is the vector (v1 , v2 , . . . ) . For example, leaving off the infinite string of zeros after the fourth place, we have DECEMBER 1996 NOTICES OF THE AMS 75 = 3 × 52 , 168 = 23 × 3 × 7, 360 = 23 × 32 × 5, 560 = 24 × 5 × 7. From these factorizations he can tell that the product of these four numbers is 210 × 34 × 54 × 72 , a square! Thus he has u2 ≡ v 2 mod n , where u = 46 · 47 · 49 · 51 ≡ 311 mod 2041, v = 25 · 32 · 52 · 7 ≡ 1416 mod 2041. He is now nearly done, since 311 6≡ ±1416 mod 2041 . Using Euclid’s algorithm to compute the greatest common factor (1416 − 311, 2041) , he finds that this is 13, and so 2041 = 13 × 157. Continued Fractions 1475 pomerance.qxp 5/7/98 9:16 AM Page 1476 v(75) = (0, 1, 2, 0), v(168) = (3, 1, 0, 1), v(360) = (3, 2, 1, 0), v(560) = (4, 0, 1, 1). For our purposes the exponent vectors give too much information. We are interested only in squares, and since a positive integer m is a square if and only if every entry of v(m) is even, we should be reducing exponents modulo 2. Since v takes products to sums, we are looking for numbers such that the sum of their exponent vectors is the zero vector mod 2. The mod 2 reductions of the above exponent vectors are v(75) ≡ (0, 1, 0, 0) mod 2, v(168) ≡ (1, 1, 0, 1) mod 2, v(360) ≡ (1, 0, 1, 0) mod 2, v(560) ≡ (0, 0, 1, 1) mod 2. Note that their sum is the zero vector! Thus the product of 75, 168, 360, and 560 is a square. To systematize this procedure, Brillhart and Morrison suggest that we choose some number B and look only at those numbers in the sequence that completely factor over the first B primes. So in the case above, we have B = 4 . As soon as B + 1 such numbers have been assembled, we have B + 1 vectors in the B-dimensional vector space F2B . By linear algebra they must be linearly dependent. But what is a linear dependence relation over the field F2? Since the only scalars are 0 and 1, a linear dependence relation is simply a subset sum equaling the 0-vector. And we have many algorithms from linear algebra that can help us find this dependency. Note that we were a little lucky here, since we were able to find the dependency with just four vectors rather than the five vectors needed in the worst case. Brillhart and Morrison call the primes p1 , p2 , . . . , pB the “factor base”. (To be more precise, they discard those primes pj for which n is not congruent to a square, since such primes will never divide a number Qi in the continuedfraction method nor a number Q(x) in Kraitchik’s method.) How is B to be chosen? If it is chosen small, then we do not need to assemble too many numbers before we can stop. But if it is chosen too small, the likelihood of finding a number in the sequence that completely factors over the first B primes will be so minuscule that it will be difficult to find even one number. Thus somewhere there is a happy balance, and with factoring 2041 via Kraitchik’s method, the happy balance turned out to be B = 4 . Some of the auxiliary numbers may be negative. How do we handle their exponent vectors? Clearly we cannot ignore the sign, since squares 1476 NOTICES OF THE AMS are not negative. However, we can put an extra coordinate in each exponent vector, one that is 0 for positive numbers and 1 for negative numbers. (It is as if we are including the “prime” −1 in the factor base.) So allowing the auxiliary numbers to be negative just increases the dimension of the problem by 1. For example, let us consider again the number 2041 and try to factor it via Kraitchik’s polynomial, but now allowing negative values. So with Q(x) = x2 − 2041 and the factor base 2, 3, and 5, we have Q(43) = −192 = −26 · 3 ↔ (1, 0, 1, 0) Q(44) = −105 Q(45) = −16 = −24 ↔ (1, 0, 0, 0) Q(46) = 75 = 3 · 52 ↔ (0, 0, 1, 0), where the first coordinates correspond to the exponent on −1 . So, using the smaller factor base of 2, 3, and 5 but allowing also negatives, we are especially lucky, since the three vectors assembled so far are dependent. This leads to the congruence (43 · 45 · 46)2 ≡ (−192)(−16) (75) mod 2041, or 12472 ≡ 4802 mod 2041 . This again gives us the divisor 13 of 2041, since (1247 − 480, 2041) = 13 . Does the final greatest common divisor step always lead to a nontrivial factorization? No it does not. The reader is invited to try still another assemblage of a square in connection with 2041. This one involves Q(x) for x = 41, 45 , and 49 and gives rise to the congruence 6012 ≡ 14402 mod 2041. In our earlier terminology, this congruence is uninteresting, since 601 ≡ −1440 mod 2041 . And sure enough, the greatest common divisor (601 − 1440, 2041) is the quite uninteresting divisor 1. Smooth Numbers and the Stirrings of Complexity Theory With the advent of the RSA public key cryptosystem in the late 1970s, it became particularly important to try to predict just how hard factoring is. Not only should we know the state of the art at present, we would like to predict just what it would take to factor larger numbers beyond what is feasible now. In particular, it seems empirically that dollar for dollar computers double their speed and capacity every one and a half to two years. Assuming this and no new factoring algorithms, what will be the state of the art in ten years? It is to this type of question that complexity theory is well suited. So how then might one analyze factoring via Kraitchik’s polynomial or the Lehmer-Powers continued fraction? Richard Schroeppel, in unpublished correspondence in the late 1970s, suggested a way. Essentially, he begins by thinking of the numbers Qi in the continued-fraction method or the numbers Q(x) in VOLUME 43, NUMBER 12 pomerance.qxp 5/7/98 9:16 AM Page 1477 Kraitchik’s method as “random”. If you are presented with a stream of truly random numbers below a particular bound X, how long should you expect to wait before you find some subset with product a square? Call a number Y-smooth if it has no prime factor exceeding Y. (Thus a number which completely factors over the primes up to pB is pB smooth.) What is the probability that a random positive integer up to X is Y -smooth? It is ψ (X, Y )/[X] ≈ ψ (X, Y )/X, where ψ (X, Y ) is the number of Y-smooth numbers in the interval [1, X] . Thus the expected number of random numbers that must be examined to find just one that is Y-smooth is the reciprocal of this probability, namely, X/ψ (X, Y ). But we must find about π (Y ) such Y-smooth numbers, where π (Y ) denotes the number of primes up to Y. So the expected number of random numbers that must be examined is about π (Y )X/ψ (X, Y ) . And how much work does it take to examine a number to see if it is Y-smooth? If one uses trial division for this task, it takes about π (Y ) steps. So the expected number of steps is π (Y )2 X/ψ (X, Y ) . It is now a job for analytic number theory to choose Y as a function of X so as to minimize the expression π (Y )2 X/ψ (X, Y ) . In fact, in the late 1970s the tools did not quite exist to make this estimation accurately. This was remedied in a paper in 1983 (see [4]), though preprints of this paper were around for several years before then. So what is the minimum?p It occurs when Y is about exp( 12 log X log p log X) and the minimum value is about exp(2 log X log log X). But what are “ X” and “ Y” anyway?1 The number X is an estimate for the typical auxiliary number the algorithm produces. In the continued-fraction method, X √ can be taken as 2 n . With Kraitchik’s polynomial, X is a little larger: it is n1/2+ε . And the number Y is an estimate for pB , the largest prime in the factor base. Thus factoring n, either via the Lehmer-Powers continued fraction or via the p Kraitchik polynomial, should take about exp( 2 log n log log n) steps. This is not a theorem; it is a conjecture. The conjecture is supported by the above heuristic argument which assumes that the auxiliary numbers generated by the continued fraction of √ n or by Kraitchik’s quadratic polynomial are “random” as far as the property of being Y-smooth goes. This has not been proved. In addition, getting many auxiliary numbers that are Y-smooth may not be sufficient for factoring n, since each time we use linear algebra over F2 to assemble the congruent squares we may be very unlucky and only come up with uninteresting solutions which do not help in the factorization. Again assuming randomness, we do not expect inordinately long strings of bad luck, and this heuristic again supports the conjecture. As mentioned, this complexity argument was first made by Richard Schroeppel in unpublished work in the late 1970s. (He assumed the result mentioned above from [4], even though at that time it was not a theorem or even really a conjecture.) Armed with the tools to study complexity, he used them during this time to come up with a new method that came to be known as the linear sieve. It was the forerunner of the quadratic sieve and also its inspiration. Using Complexity to Come Up With a Better Algorithm: The Quadratic Sieve a student in elementary algebra, not to mention many a philosopher of mathematics. The above complexity sketch shows a place where we might gain some improvement. It is the time we are taking to recognize auxiliary numbers that factor completely with the primes up to Y = pB, that is, the Y-smooth numbers. In the argument we assumed this is about π (Y ) steps, where π (Y ) is the number of primes up to Y. The probability that a number is Y-smooth is, according to the notation above, ψ (X, Y )/[X] . As you might expect and as is easily checked in practice, when Y is a reasonable size and X is very large, this probability is very, very small. So one after the other, the auxiliary numbers pop up, and we have to invest all this time in each one, only to find out almost always that the number is not Y-smooth and is thus a number that we will discard. It occurred to me early in 1981 that one might use something akin to the sieve of Eratosthenes to quickly recognize the smooth values of Kraitchik’s quadratic polynomial Q(x) = x2 − n. The sieve of Eratosthenes is the well-known device for finding all the primes in an initial interval of the natural numbers. One circles the first prime 2 and then crosses off every second number, namely, 4, 6, 8, etc. The next unmarked number is 3. It is circled, and we then cross off every third number. And so on. After reaching the square root of the upper limit of the sieve, one can stop the procedure and circle every remaining unmarked number. The circled numbers are the primes; the crossed-off numbers the composites. It should be noted that the sieve of Eratosthenes does more than find primes. Some crossed-off numbers are crossed off many times. For example, 30 is crossed off three times, as is 42, since these numbers have three prime factors. Thus we can quickly scan the array looking for numbers that are crossed off a lot and so quickly find the numbers which have many DECEMBER 1996 NOTICES OF THE AMS 1Actually, this is a question that has perplexed many 1477 pomerance.qxp 5/7/98 9:16 AM Page 1478 prime factors. And clearly there is a correlation between having many prime factors and having all small prime factors. But we can do better than have a correlation. By dividing by the prime, instead of crossing off, numbers like 30 and 42 get transformed to the number 1 at the end of the sieve, since they are completely factored by the primes used in the sieve. So instead of sieving with the primes up to the square root of the upper bound of the sieve, say we only sieve with the primes up to Y. And instead of crossing a number off, we divide it by the prime. At the end of the sieve any number that has been changed to the number 1 is Y-smooth. But not every Y-smooth is caught in this sieve. For example, 60 gets divided by its prime factors and is changed to the number 2. The problem is higher powers of the primes up to Y. We can rectify this by also sieving by these higher powers and dividing hits by the underlying prime. Then the residual 1’s at the end correspond exactly to the Y-smooth numbers in the interval. The time for doing this is unbelievably fast compared with trial dividing each candidate number to see if it is Y-smooth. If the length of the interval is N , the number of steps is only about N log log Y , or about log log Y steps on average per candidate. So we can quickly recognize Y-smooth numbers in an initial interval. But can we use this idea to recognize Y-smooth values of the quadratic polynomial Q(x) = x2 − n? What it takes for a sieve to work is that for each modulus m in the sieve, the multiples of the number m appear in regular places in the array. So take a prime p, for example, and ask, For which values of x do we have Q(x) divisible by p? This is not a difficult problem. If n (the number being factored) is a nonzero square modulo p, then there are two residue classes a and b mod p such that Q(x) ≡ 0 mod p if and only if x ≡ a or b mod p. If n is not a square modulo p, then Q(x) is never divisible by p and no further computations with p need be done. So essentially the same idea can be used, and we can recognize the Y-smooth values of Q(x) in about log log Y steps per candidate value. What does the complexity argument give us? The p time to factor n is now about √ exp( log n log log n) ; namely, the factor 2 in the exponent is missing. Is this a big deal? You bet. This lower complexity and other friendly features of the method allowed a twofold increase in the length of the numbers that could be factored (compared with the continued-fraction method discussed above). And so was born the quadratic sieve method as a complexity argument and with no numerical experiments. 1478 NOTICES OF THE AMS Implementations and Enhancements In fact, I was very lucky that the quadratic sieve turned out to be a competitive algorithm. More often than not, when one invents algorithms solely via complexity arguments and thought experiments, the result is likely to be too awkward to be a competitive method. In addition, even if the basic idea is sound, there well could be important enhancements waiting to be discovered by the people who actually try the thing out. This in fact happened with the quadratic sieve. The first person to try out the quadratic sieve method on a big number was Joseph Gerver (see [9]). Using the task as an opportunity to learn programming, he successfully factored a 47-digit number from the Cunningham project. This project, begun early in this century by Lt.-Col. Allan J. Cunningham and H. J. Woodall, consists of factoring into primes the numbers bn ± 1 for b up to 12 (and not a power) and n up to high numbers (see [3]). Gerver’s number was a factor of 3225 − 1 . Actually I had a hard time getting people to try out the quadratic sieve. Many Cunningham project factorers seemed satisfied with the continued-fraction method, and they thought that the larger values of Kraitchik’s polynomial Q(x) , compared with the numbers Qi in the continued-fraction method, was too great a handicap for the fledgling quadratic sieve method. But at a conference in Winnipeg in the fall of 1982, I convinced Gus Simmons and Tony Warnock of Sandia Laboratories to give it a try on their Cray computer. Jim Davis and Diane Holdridge were assigned the task of coding up the quadratic sieve on the Sandia Cray. Not only did they succeed, but they quickly began setting records. And Davis found an important enhancement that mitigated the handicap mentioned above. He found a way of switching to other quadratic polynomials after values of the first one, Q(x) = x2 − n, grew uncomfortably large. Though this idea did not substantially change the complexity estimate, it made the method much more practical. Their success not only made the cover of the Mathematical Intelligencer (the volume 6, number 3 cover in 1984 had on it a Cray computer and the factorization of the number consisting of 71 ones), but there was even a short article in Time magazine, complete with a photo of Simmons. It was ironic that shortly before the Sandia team began this project, another Sandia team had designed and manufactured an RSA chip for public key cryptography, whose security was based on our inability to factor numbers of about 100 digits. Clearly this was not safe enough, and the chip had to be scrapped. VOLUME 43, NUMBER 12 Around this time Peter Montgomery independently came up with another, slightly better way of changing polynomials, and we now use his method rather than that of Davis. One great advantage of the quadratic sieve method over the continued-fraction method is that with the quadratic sieve it is especially easy to distribute the task of factoring to many computers. For example, using multiple polynomials, each computer can be given its own set of quadratic polynomials to sieve. At first, the greatest successes of the quadratic sieve came from supercomputers, such as the Cray XMP at Sandia Laboratories. But with the proliferation of low-cost workstations and PCs and the natural way that the quadratic sieve can be distributed, the records passed on to those who organized distributed attacks on target numbers. Robert Silverman was the first to factor a number using many computers. Later, Red Alford and I used over 100 very primitive, nonnetworked PCs to factor a couple of 100-digit numbers (see [2]). But we did not set a record, because while we were tooling up, Arjen Lenstra and Mark Manasse [12] took the ultimate step in distributing the problem. They put the quadratic sieve on the Internet, soliciting computer time from people all over the world. It was via such a shared effort that the 129-digit RSA challenge number was eventually factored in 1994. This project, led by Derek Atkins, Michael Graff, Paul Leyland, and Lenstra, took about eight months of real time and involved over 1017 elementary steps. The quadratic sieve is ultimately a very simple algorithm, and this is one of its strengths. Due to its simplicity one might think that it could be possible to design a special-purpose computer solely dedicated to factoring big numbers. Jeff Smith and Sam Wagstaff at the University of Georgia had built a special-purpose processor to implement the continued-fraction method. Dubbed the “Georgia Cracker”, it had some limited success but was overshadowed by quadratic sieve factorizations on conventional computers. Smith, Randy Tuler, and I (see [21]) thought we might build a special-purpose quadratic sieve processor. “Quasimodo”, for Quadratic Sieve Motor, was built but never functioned properly. The point later became moot due to the exponential spread of low-cost, highquality computers. The Dawn of the Number Field Sieve Taking his inspiration from a discrete logarithm algorithm of Don Coppersmith, Andrew Odlyzko, and Richard Schroeppel [6] that used quadratic number fields, John Pollard in 1988 circulated a letter to several people outlining an idea of his for factoring certain big numbers via algebraic DECEMBER 1996 Photograph courtesy of the Computer Museum, Boston, MA. pomerance.qxp 5/7/98 9:16 AM Page 1479 Modern model of the Lehmer Bicycle Chain Sieve constructed by Robert Canepa and currently in storage at the Computer Museum, 300 Congress Street, Boston, MA 02210. number fields. His original idea was not for any large composite, but for certain “pretty” composites that had the property that they were close to powers and had certain other nice properties as well. He illustrated the idea with a fac7 torization of the number 22 + 1, the seventh Fermat number. It is interesting that this number was the first major success of the continued-fraction factoring method, almost twenty years earlier. I must admit that at first I was not too keen on Pollard’s method, since it seemed to be applicable to only a few numbers. However, some people were taking it seriously, one being Hendrik Lenstra. He improved some details in the algorithm and, along with his brother Arjen and Mark Manasse, set about using the method to factor several large numbers from the Cunningham project. After a few successes (most notably a 138-digit number) and after Brian LaMacchia and Andrew Odlyzko had made some inroads in dealing with the large, sparse matrices that come up in the method, the Lenstras and Manasse set 9 their eyes on a real prize, 22 + 1, the ninth Fermat number.2 Clearly it was beyond the range of the quadratic sieve. Hendrik Lenstra’s own elliptic curve method, which he discovered early 2This number had already been suggested in Pollard’s original note as a worthy goal. It was known to be composite—in fact, we already knew a 7-digit prime factor— but the remaining 148-digit cofactor was still composite, with no factor known. NOTICES OF THE AMS 1479 pomerance.qxp 5/7/98 9:16 AM Page 1480 in 1985 and which is especially good at splitting numbers which have a relatively small prime factor (say, “only” 30 or so digits) had so far not been of help in factoring it. The Lenstras and Manasse succeeded in getting the prime factor9 ization of 22 + 1 in the spring of 1990. This sensational achievement announced to the world that Pollard’s number field sieve had arrived. But what of general numbers? In the summer of 1989 I was to give a talk at the meeting of the Canadian Number Theory Association in Vancouver. It was to be a survey talk on factoring, and I figured it would be a good idea to mention Pollard’s new method. On the plane on the way to the meeting I did a complexity analysis of the method as to how it would work for general numbers, assuming myriad technical difficulties did not exist and that it was possible to run it for general numbers. I was astounded. The complexity for this algorithm-that-did-not-yetexist was of the shape exp(c(log n)1/3 (log log n)2/3 ) . The key difference over the complexity of the quadratic sieve was that the most important quantity in the exponent, the power of log n, had its exponent reduced from 1/2 to 1/3. If reducing the constant in the exponent had such a profound impact in passing from the continued-fraction method to the quadratic sieve, think what reducing the exponent in the exponent might accomplish. Clearly this method deserved some serious thought! I do not wish to give the impression that with this complexity analysis I had single-handedly found a way to apply the number field sieve to general composites. Far from it. I merely had a shrouded glimpse of exciting possibilities for the future. That these possibilities were ever realized was mostly due to Joe Buhler, Hendrik Lenstra, and others. In addition, some months earlier Lenstra had done a complexity analysis for Pollard’s method applied to special numbers, and he too arrived at the expression exp(c(log n)1/3 (log log n)2/3 ) . My own analysis was based on some optimistic algebraic assumptions and on arguments about what might be expected to hold, via averaging arguments, for a general number. The starting point of Pollard’s method to factor n is to come up with a monic polynomial f (x) over the integers that is irreducible and an integer m such that f (m) ≡ 0 mod n. The polynomial should have “moderate” degree d , meaning that if n has between 100 and 200 digits, then d should be 5 or 6. For a number such as the 9 ninth Fermat number, n = 22 + 1 , it is easy to come up with such a polynomial. Note that 8n = 2515 + 8 . So let f (x) = x5 + 8 , and let m = 2103 . Of what possible use could such a polynomial be? Let α be a complex root of f (x), and consider 1480 NOTICES OF THE AMS the ring Z[α] consisting of all polynomial expressions in α with integer coefficients. Since f (α) = 0 and f (m) ≡ 0 mod n, by substituting the residue m mod n for each occurrence of α we have a natural map φ from Z[α] to Z/(nZ) . Our conditions on f , α, and m ensure that φ is well defined. And not only this, φ is a ring homomorphism. Suppose now that S is a finite set of coprime integer pairs ha, bi with two properties. The first is that the product of the algebraic integers a − αb for all pairs ha, bi in S is a square in Z[α] , say, γ 2 . The second property for S is that the product of all the numbers a − mb for pairs ha, bi in S is a square in Z , say, v 2 . Since γ may be written as a polynomial expression in α, we may replace each occurrence of α with the integer m , coming up with an integer u with φ(γ) ≡ u mod n. Then Y 2 2 2 u ≡ φ(γ) = φ(γ ) = φ (a − αb) = Y ha,bi∈S φ(a − αb) ha,bi∈S ≡ Y (a − mb) = v 2 mod n. ha,bi∈S And we know what to do with u and v . Just as Kraitchik showed us seventy years ago, we hope that we have an interesting congruence, that is, u 6≡ ±v mod n, and if so, we take the greatest common divisor (u − v, n) to get a nontrivial factor of n. Where is the set S of pairs ha, bi supposed to come from? For at least the second property S is supposed to have, namely, that the product of the numbers a − mb is a square, it is clear we might again use exponent vectors and a sieve. Here there are two variables a and b instead of just the one variable in Q(x) in the quadratic sieve. So we view this as a parametrized family of linear polynomials. We can fix b and let a run over an interval, then change to the next b and repeat. But S is to have a second property too: for the same pairs ha, bi , the product of a − αb is a square in Z[α] . It was Pollard’s thought that if we were in the nice situation that Z[α] is the full ring of algebraic integers in Q(α) , if the ring is a unique factorization domain, and if we know a basis for the units, then we could equally well create exponent vectors for the algebraic integers a − αb and essentially repeat the same algorithm. To arrange for both properties of S to hold simultaneously, well, this would just involve longer exponent vectors having coordinates for all the small prime numbers, for the sign of a − αb , for all the “small” primes in Z[α] , and for each unit in the unit basis. But how are we supposed to do this for a general number n? In fact, how do we even VOLUME 43, NUMBER 12 pomerance.qxp 5/7/98 9:16 AM Page 1481 achieve the first step of finding the polynomial f (x) and the integer m with f (m) ≡ 0 mod n? And if we could find it, why should we expect that Z[α] has all of the nice properties to make Pollard’s plan work? The Number Field Sieve Evolves There is at the least a very simple device to get started, that is, to find f (x) and m. The trick is to find f (x) last. First, one decides on the degree d of f . Next, one lets m be the integer part of n1/d . Now write n in the base m , so that n = md + cd−1 md−1 + · · · + c0 , where the base m “digits” ci satisfy 0 ≤ ci < m . (If n > (2d)d , then the leading “digit” cd is 1.) The polynomial f (x) is now staring us in the face; it is xd + cd−1 xd−1 + · · · + c0 . So we have a monic polynomial f (x), but is it irreducible? There are many strategies for factoring primitive polynomials over Z into irreducible factors. In fact, we have the celebrated polynomial-time algorithm of Arjen Lenstra, Hendrik Lenstra, and Lászlo Lovász for factoring primitive polynomials in Z[x] (the running time is bounded by a fixed power of the sum of the degree and the number of digits in the coefficients). So suppose we are unlucky and the above procedure leads to a reducible polynomial f (x) , say, f (x) = g(x)h(x). Then n = f (m)