Reference / Paper · 1993
The Factorization of the Ninth Fermat Number (Math. Comp. 61, 319–349)
The first factorisation by the number field sieve.
Reference / Paper · 1993
The first factorisation by the number field sieve.
MATHEMATICSOF COMPUTATION VOLUME61, NUMBER203 JULY 1993,PAGES319-349 THE FACTORIZATION OF THE NINTH FERMAT NUMBER A. K. LENSTRA, H. W. LENSTRA,JR., M. S. MANASSE,AND J. M. POLLARD Dedicated to the memory ofD. H. Lehmer Abstract. In this paper we exhibit the full prime factorization of the ninth Fermât number Fg = 2512+ 1 . It is the product of three prime factors that have 7, 49, and 99 decimal digits. We found the two largest prime factors by means of the number field sieve, which is a factoring algorithm that depends on arithmetic in an algebraic number field. In the present case, the number field used was Q(v^2). The calculations were done on approximately 700 workstations scattered around the world, and in one of the final stages a supercomputer was used. The entire factorization took four months. Introduction For a nonnegative integer k , the kth Fermât number Fk is defined by Fk 22 4- 1. The ninth Fermât number Fy = 2512+ 1 has 155 decimal digits: F9 = 13407807929942597099574024998205846127479365820592393 377723561443721764030073546976801874298166903427690031 858186486050853753882811946569946433649006084097. It is the product of three prime numbers: F<) = Pi • P49 • P99 , where p7, p49 , and p99 have 7, 49, and 99 decimal digits: p7 = 2424833, P49= 7455602825647 884208 337395 736200454918 783366 342657, p99= 741 640062627530 801524 787141 901937474059940781 097519 023905 821316144415 759504705008092818 711693940737. In binary, p7, p49, and P99 have 22, 163, and 329 digits: Received by the editor March 4, 1991 and, in revised form, August 3, 1992. 1991 Mathematics Subject Classification. Primary 11Y05, 11Y40. Key words and phrases. Fermât number, factoring algorithm. ©1993 American Mathematical Society 0025-5718/93 $1.00+ $.25 per page 319 320 Pi P49 P99 A. K. LENSTRA, H. W. LENSTRA, JR., M. S. MANASSE,AND J. M. POLLARD 1001010000000000 000001, 1010001100111110000110010110001010011001111001101 101100111111001101 101001 111101000010001111 101010110010 101101010111 100000110001010011001001010101 000010 100000 000001, 10101101100110110001111010110100000010011100101010000 101110011110100011001010111000110001111001100101110011 010011000110111110011000100110010101001011000101100110 011110000110110010000110111011001010010110001100001011 111111111001001000101010101001111010100011001001111010 010100000000101101101010111001000100110001101101100000 000001. The binary representation of F9 itself consists of 511 zeros surrounded by 2 ones. In this paper we discuss several aspects of the factorization of the ninth Fermât number. Section 1 is devoted to Fermât numbers and their place in number theory and its history. In §2 we address the general problem of factoring integers, and we describe the basic technique that many modern factoring methods rely on. In §3 we return to the ninth Fermât number, and we explain why previous factoring attempts of Fg failed. We factored the number by means of the number field sieve. This method depends on a few basic facts from algebraic number theory, which are reviewed in §4. Our account of the number field sieve, in §5, can be read as an introduction to the more complete descriptions that are found in [28] and [10]. The actual sieving forms the subject of §6. The final stage of the factorization of Fa , which involved the solution of a huge linear system, is recounted in §7. 1. Fermât numbers Fermât numbers were first considered in 1640 by the French mathematician Pierre de Fermât (1601-1665), whose interest in the problem of factoring integers of the form 2m ± 1 arose from their connection with "perfect", "amicable", and "submultiple" numbers [47; 48, Chapter II, §IV]. He remarked that a number of the form 2m + 1 , where m is a positive integer, can be prime only if m is a power of 2, which makes 2m + 1 a Fermât number. A Fermât number that is prime is called a Fermât prime. Fermât repeatedly expressed his strong belief that all Fermât numbers were prime. Apparently, this belief was based on his observation that each prime divisor p of Fk must satisfy a strong condition, namely p = 1 mod 2k+l . In present-day language, one would formulate his proof of this as follows. If 22 = -1 modp, then (2 modp) has multiplicative order 2k+l , and so 2k+] divides p - 1 , by Fermat's own "little" theorem, which also dates from 1640. It is not clear whether Fermât was aware of the stronger condition p = 1 mod 2k+2 for prime divisors p of Fk , k > 2. To prove this, it suffices to replace (2 mod p), in the argument above, by its square root (22 (22 - 1) mod p), which has order 2^+2. (It is THE FACTORIZATIONOF THE NINTH FERMAT NUMBER 321 amusing to note that also (Fk_\ modp) has order 2k+1, because its square is an odd power of (2 modp).) Incidentally, from the binary representations of the prime factors of F9 we see that ord2(p7 - 1) = 16, ord2(p49 - 1) = 11, ord2(p99 - 1) = 11, where ord2 counts the number of factors 2. The first five Fermât numbers Fq = 3, F\ = 5, F2 = 17, Ft, = 257, and F4 = 65537 are indeed prime, but to this day these remain the only known Fermât primes. Nowadays it is considered more likely, on loose probabilistic grounds, that there are only finitely many Fermât primes. It may well be that F0 through F4 are the only ones. On similar grounds, it is considered likely that all Fermât numbers are squarefree, with perhaps finitely many exceptions. As for F$, Fermât knew that any prime divisor of F$ must be among 193, 449, 577, 641, 769, ... , which is the sequence of primes that are 1 mod 26, with Ft, = 257 omitted (distinct Fermât numbers are clearly relatively prime). Thus it is difficult to understand how he missed the factor 641, which is only the fourth one to try; among those that are 1 mod 27, it is the first! One is led to believe that Fermât did not seriously attempt to verify his conjecture numerically, or that he made a computational error if he did. The factor 641 of F5 was found by Euler in 1732, who thereby refuted Fermat's belief [18]. The cofactor /75/641 = 6700417 is also prime. Gauss showed in 1801 that Fermât primes are of importance in elementary geometry: a regular Tz-goncan be constructed with ruler and compasses if and only if 77 is the product of a power of 2 and a set of distinct Fermât primes [19]. Since the second half of the nineteenth century, many mathematicians have been intrigued by the problem of finding prime factors of Fermât numbers and, more generally, numbers of the form 2m ± 1 . Somewhat later, this interest was extended to the larger class of Cunningham numbers bm ± 1 (with b small and m large) [16, 7]. The best factoring algorithms were usually applied to these numbers, so that the progress made in the general area of factoring large integers was reflected in the factorization of Fermât and Cunningham numbers. The effort required for the complete prime factorization of a Fermât number may be expected to be substantially larger than for the preceding one, since the latter has only half as many digits (rounded upwards) as the former. In several cases the factorization could be accomplished only by means of a newly invented method. In 1880, Landry factored F6, but his method was never published (see [25; 17, Chapter XV, p. 377; 20; 50]). In 1970, Morrison and Brillhart found the factorization of Fi with the continued fraction method [36]. Brent and the fourth author factored F% in 1980 by means of a modified version of Pollard's rho method [6]. In 1-988, Brent used the elliptic curve method to factor Fu (see [4, 5]). Most recently, F<) was factored in 1990 by means of the number field sieve. Unlike methods previously used, the number field sieve is far more effective on Fermât and Cunningham numbers than on general numbers. Factoring general numbers of the order of magnitude of Fx, with the number field sieve—or with any other known method—requires currently substantially more time and financial resources than were spent on F9 ; and factoring general numbers of the order of magnitude of lO15/^ is not yet practically feasible. 322 A. K. LENSTRA, H. W. LENSTRA, JR., M. S. MANASSE,AND J. M. POLLARD The fact that the number field sieve performs abnormally well on Fermât and Cunningham numbers implies that these numbers are losing their value as a yardstick to measure progress in factoring. One wonders which class of numbers will take their place. Good test numbers for factoring algorithms should meet several conditions. They should be defined a priori, to avoid the impression that the factored numbers were generated by multiplying known factors. They should be easy to compute. They should not have known arithmetic properties that might be exploited by a special factorization algorithm. For any size range, there should be enough test numbers so that one does not quickly run out, but few enough to spark competition for them. They should have some mathematical significance, so that factoring them is a respectable activity. The last condition is perhaps a controversial one; but do we want to factor numbers that are obtained from a pseudorandom number generator, or from the digits of n (see [2, 44])? The values of the partition function [1] meet the conditions above reasonably well, although they appear to be too highly divisible by small primes. In addition, their factorization is financially attractive (see [42]). We offer them to future factorers as test numbers. Nonetheless, factoring Fermât numbers remains a challenging problem, and it is likely to exercise a special fascination for a long time to come. In addition to the more or less general methods mentioned above, a very special method has been used to search for factors of Fermât numbers. It proceeds not by fixing k and searching for numbers p dividing Fk , but by fixing p and searching for numbers k with Fk = 0 mod p . To do this, one first chooses a number p = u • 2l + 1 , with u odd and / relatively large, that is free of small prime factors; one can do this by fixing one of u, / and sieving over the other. Next one determines, by repeated squarings modulo p, the residue classes (22 mod p), k -2,3, ... . From what we proved above about prime factors of Fermât numbers it follows that if no value k < I -2 is found with 22 = —1 mod p , then p does not divide any Fk , k > 2 ; in this case p is tk discarded. If a value of k is found with 22 = -1 mod p—which one expects, loosely, to happen with probability l/u , if p is prime—then p is a factor of Fk . The primality of p is then usually automatic from knowledge that one may have about smaller prime factors of Fk or, if p is sufficiently small, from the fact that all its divisors are 1 mod 2k+2. Many factors of Fermât numbers have been found by the method just sketched. In 1903, A. E. Western [15] found the prime factor p7 = 2424833 = 37 • 216 + 1 of F9. In 1984, Keller found the prime factor 5 • 223473+ 1 of /«23471; the latter number is the largest Fermât number known to be composite. If no factor of Fk can be found, one can apply a primality test that is essentially due to Pepin [37]: for k > 1 , the number Fk is prime if and only if 3(**-i)/2 = _i mo(j fk xhis congruence can be checked in time 0((lo$Fk)3), and in time 0((logFk)2+e) (for any positive e) if one uses fast multiplication techniques. One should not view Pepin's test as a polynomial-time algorithm, however. In fact, the input is k , and from log Fk « 2k log 2 we see that the time that the test takes is a doubly exponential function of the length (log k)/ log 2 of the input. Pepin's test has indeed been applied only for a very limited collection of values of k . Known factors of Fk can be investigated for primality by means of general THE FACTORIZATION OF THE NINTH FERMAT NUMBER 323 primality tests. In this way, Brillhart [22, p. 110] found in 1967 that the number 7*9/2424833, which has 148 decimal digits, is composite. In 1988, Brent and Morain found that F[ i divided by the product of four relatively small prime factors is a prime number of 564 decimal digits, thereby completing the prime factorization of Fu . The many results on factors of Fermât numbers that have been obtained by the methods above, as well as bibliographic information, can be found in [17, Chapter XV; 16, 7, 41, 23]. For up-to-date information one should consult the current issues of Mathematics of Computation, as well as the updates to [7] that are regularly published by S. S. Wagstaff, Jr. We give a brief summary of the present state of knowledge. The complete prime factorization of Fk is known for k < 9, for k = 11 , and for no other k . One or more prime factors of Fk are known for all k < 32 except k = 14, 20, 22, 24, 28, and 31, as well as for 76 larger values of k , the largest being k = 23471. For k = 10, 12, 13, 15, 16, 17, and 18 the cofactor is known to be composite. No nontrivial factor is known of i7^ or F2o, but it is known that these numbers are composite. For k = 22, 24, 28, 31, and all except 76 values of k > 32, it is unknown whether Fk is prime or composite. The smallest Fermât number that has not been completely factored is Fio. Its known prime factors are 11131 -212 + 1 =45 592577, 395937 -214+1 =6487 031809. The cofactor has 291 decimal digits. Unless it has a relatively small factor, it is not likely to be factored soon. The factorization of Fermât numbers is of possible interest in the theory of finite fields. Let m be a nonnegative integer, and let the field K be obtained by m successive quadratic extensions of the two-element field, so that # K —22™; an elegant explicit description of K was given by Conway [14, Chapter 6] and another by Wiedemann [49]. It is easy to see that the multiplicative group of K is a direct sum of 777cyclic groups of orders Fq, F\, ... , Fm-x . Therefore, knowledge of the prime factors of Fermât numbers is useful if one wishes to determine the multiplicative order of a given nonzero element of K, or if one searches for a primitive root of K. 2. Factoring integers In this section, n is an odd integer greater than 1. It should be thought of as an integer that we want to factor into primes. We denote by Z the ring of integers, by Z/77Z the ring of integers modulo n , and by (Z/nZ)* the group of units (i.e., invertible elements) of Z/nZ. 2.1. Factoring with square roots of 1. The subgroup {x e Z/nZ : x2 = 1} of (Z/nZ)* may be viewed as a vector space over the two-element field F2 = Z/2Z, the vector addition being given by multiplication. Many factoring algorithms depend on the elementary fact that the dimension of this vector space is equal to the number of distinct prime factors of n. In particular, if n is not a power of a prime number, then there is an element x e Z/nZ, x ^ ±1, 324 A. K. LENSTRA,H. W. LENSTRA,JR., M. S. MANASSE,AND J. M. POLLARD such that x2 = 1 . Moreover, explicit knowledge of such an element x, say x = (y mod n), leads to a nontrivial factorization of 77. Namely, from y2 = 1 mod n , y ^ ± 1 mod n , it follows that n divides the product of y - 1 and y 4-1 without dividing the factors, so that gcd(>>- 1, n) and gcd(y 4-1, n) are nontrivial divisors of n . They are in fact complementary divisors, so that only one of the gcd's needs to be calculated; this can be done with Euclid's algorithm. We conclude that, to factor 77, it suffices to find x e Z/77Z with x2= 1 , x^±l. 2.2. Repeated prime factors. The procedure just sketched will fail if 77 is a prime power, so it is wise to rule out that possibility before attempting to factor n in this way. To do this, one can begin by subjecting 77 to a primality test, as in [27, §5]. If n is prime, the factorization is finished. Suppose that n is not prime. One still needs to check that n is not a prime power. This check is often omitted, since in many cases it is considered highly unlikely that n is a prime power if it is not prime; it may even be considered highly likely that n is squarefree, that is, not divisible by the square of a prime number. For example, suppose that 77 is the unfactored portion of some randomly drawn integer, and one is certain that it has no prime factor below a certain bound B. Then the probability for n not to be squarefree is 0{l/(BlogB)), in a sense that can be made precise, and the probability that « is a proper power of a prime number is even smaller. A similar statement may be true if n is the unfactored portion of a Cunningham number, since, to our knowledge, no such number has been found to be divisible by the square of a prime factor that was difficult to find. Whether other classes of test numbers that one may propose behave similarly remains to be seen; if the number 77to be factored is provided by a "friend", or by a colleague who does not yet have sufficient understanding of the arithmetical properties of the numbers that his computations produce, it may be unwise to ignore the possibility of repeated prime factors. 2.3. Squarefreeness tests. No squarefreeness tests for integers are known that are essentially faster than factoring (see [9, §7]). This is often contrasted with the case of polynomials in one variable over a field K , in which case it suffices to take the gcd with the derivative. This illustrates that for many algorithmic questions the well-known analogy between Z and K[X] appears to break down. Note also that for many fields K, including finite fields and algebraic number fields, there exist excellent practical factoring algorithms for K[X] (see [26]). which have no known analogue in Z. There do exist factoring methods that become a little faster if one wishes only to test squarefreeness; for example, if n is not a square—which can easily be tested—then to determine whether or not n is squarefree it suffices to do trial division up to tí1/3 instead of nx¡2. There is also a factoring method that has great difficulties with numbers n that are not squarefree. Suppose, for example, that p is a large prime for which p - 1 and p + 1 both have a large prime factor, and that 77 has exactly two factors p. The factoring method described in [43], which depends on the use of "random class groups", does not have a reasonable chance of finding any nontrivial factor of n, at least not within the time that is conjectured in [43] (see [32, §11]). THE FACTORIZATIONOF THE NINTH FERMAT NUMBER 325 2.4. Recognizing powers. Ruling out that 77 is a prime power is much easier than testing n for squarefreeness. One way to proceed is by testing that n is not a proper power. Namely, if n = m1, where m , I are integers and / > 1, then m > 3, 2 < / < [(logn)/ log 3], and one may assume that / is prime. Hence, the number of values to be considered for / is quite small, and this number can be further reduced if a better lower bound for m is known, such as a number B as in §2.2. For each value of /, one can calculate an integer mo for which |wo - nxl'\ < 1, using Newton's method, and test whether n = mlQ; this is the case if and only if n is an /th power. One can often save time by calculating wo only if n satisfies the conditions n'-l = l modi2 (mod 8 if/= 2) and „(i-D//sl modtf for several small primes q with q = 1 mod /. These are necessary conditions for a number n that is free of small prime factors to be an /th power, if / is prime. 2.5. Ruling our prime powers. There is a second, less well-known way to proceed, which tests only that n is not a prime power. It assumes that one has already proved that n is composite by means of Fermat's theorem, which states that a" = a mod n for every integer a, if n is prime. Hence, if an integer a has been found for which a" ^ a mod n , then one is sure that n is composite. If 71 is a prime power, say n = pk , then Fermat's theorem implies that aP = a mod p and hence also that a" = ap = a mod p ; that is, p divides a" - a, so it also divides gcd(a" -a, n). This suggests the following approach. Having found an integer a for which (an - a mod n) is nonzero, we calculate the gcd of that number with n . If the gcd is 1, we can conclude that n is not a prime power. If the gcd is not 1, then the gcd is a nontrivial factor of 77, which is usually more valuable than the information that n is or is not a prime power. Nowadays one often proves compositeness by using a variant of Fermat's theorem that depends on the splitting i-i a"-a = a-(au- 1) • Y[{au'2' + 1), !=0 where « - 1 = u • 2', with u odd and / = ord2(7z - 1). Hence, if n is prime, then for any integer a one of the 14- 2 factors on the right is divisible by n . This variant has the advantage that the converse is true in a strong sense: if n is not prime, then most integers a have the property that none of the factors on the right is 0 mod 77 (see [40] for a precise statement and proof); such integers a are called witnesses to the compositeness of n . Currently, if one is sure that the number n to be factored is composite, it is usually because one has found such a witness. Just as above, a witness a can be used to check that n is in fact not a prime power: calculate a" - a (mod n), which one does most easily by first squaring the number a"'2' (mod 77) that was last calculated; if it is nonzero, one verifies as before that gcd(a" - a, n) = 1, and if it is zero then one of the t + 2 factors on the right has a nontrivial factor in common with 77, which can readily be found. (In the latter case, 77 is in fact not a prime power, since the odd parts of the 14-2 factors are pairwise relatively prime.) 326 A. K. LENSTRA,H. W. LENSTRA,JR., M. S. MANASSE,AND J. M. POLLARD As we mentioned in §1, the number 7^/2424833 was proved to be composite by Brillhart in 1967. We do not know whether he or anybody else proved that it is not a prime power until this fact became plain from its prime factorization. We did not, not because we thought it was not worth our time, but simply because we did not think of it. If it had been a prime power, our method would have failed completely, and we would have felt greatly embarrassed towards the many people who helped us in this project. One may believe that the risk that we were unconsciously taking was extremely small, but until the number was factored this was indeed nothing more than a belief. In any case, it would be wise to include, in the witness test described above, the few extra lines that prove that the number is not a prime power, and to explicitly publish this information about a number rather than just saying that it is composite. 2.6. A general scheme. For the rest of this section we assume that n , besides being odd and greater than 1, is not a prime power. We wish to factor 77 into primes. As we have seen, each x e Z/77Z with x2 = 1 , x / ± 1 gives rise to a nontrivial factor of n . In fact, it is not difficult to see that the full factorization of n into powers of distinct prime numbers can be obtained from a set of generators of the F2-vector space {x e Z/nZ:x2 — 1}. (If we make this vector space into a Boolean ring with x*y = (1 + x4y-xy)/2 as multiplication, then a set of ring generators also suffices.) The question is how to determine such a set of generators. Several algorithms have been proposed to do this, most of them following some refinement of the following scheme. Step 1. Selecting the factor base. Select a collection of nonzero elements ap E Z/nZ, with p ranging over some finite index set P. How this selection takes place depends on the particular algorithm; it is usually not done randomly, but in such a way that Step 2 below can be performed in an efficient manner. The collection {ap)pep is called the factor base. We shall assume that all ap are units of Z/77Z. In practice, this is likely to be true, since if 77 is difficult to factor, one does not expect one of its prime factors to show up in one of the ap 's; one can verify the assumption, or find a nontrivial factor of 77, by means of a gcd computation. Denote by Zp the additive abelian group consisting of all vectors (vp)pep with u^eZ, and let /: Zp —>(Z/nZ)* be the group homomorphism (from an additively to a multiplicatively written group) that sends (vp)p€P l° Iloepap ■ This map is surjective if and only if the elements ap generate (Z/77Z)*. For the choices of ap that are made in practice that is usually the case, although we are currently unable to prove this. (In general, hardly anything has been rigorously proved about practical factoring algorithms.) Step 2. Collecting relations. Each element v = {vp)peP of the kernel of / is a relation between the ap, in the sense that n/;ep a"p = 1 • In the second step, one looks for such relations by a method that depends on the algorithm. One stops as soon as the collection V of relations that have been found has slightly more than # P elements. One hopes that V generates the kernel of f. although this is again typically beyond proof. Note that the kernel of / is of finite index in Zp, so that by a well-known theorem from algebra it is freely generated by # P elements; therefore, the hope is not entirely unreasonable. Step 3. Finding dependencies. For each v e V , let v e (Z/2Z)P = FP be the vector that one obtains from v by reducing its coordinates modulo 2. Since # V > # P, the vectors v are linearly dependent over F2. In Step 3, one finds THE FACTORIZATIONOF THE NINTH FERMAT NUMBER 327 explicit dependencies by solving a linear system. The matrix that describes the system tends to be huge and sparse, which implies that special methods can be applied (see [24]). Nevertheless, one usually employs ordinary Gaussian elimination. The size of the matrices may make it desirable to modify Gaussian elimination somewhat; see §7. Each dependency that is found can be written in the form Zvew^ = ® f°r some subset W c V, and each such subset gives rise to a vector tu = (Zvewv)ß e ^P f°r wmcn 2 • w belongs to the kernel of /. Each such w, in turn, gives rise to an element x = f(w) £ (Z/nZ)* satisfying x2 = /(2 • w) = 1, and therefore possibly to a decomposition of n into two nontrivial factors. If the factorization is trivial (because x = ± 1), or, more generally, if the factors that are found are themselves not prime powers, then one repeats the same procedure starting from a different dependency between the vectors v. Note that it is useless to use a dependency that is a linear combination of dependencies that have been used earlier. Also, if several factorizations of 77into two factors are obtained, they should be combined into one factorization of n into several factors by a few gcd calculations. One stops when all factors are prime powers; if indeed / is surjective and V generates the kernel of /, this is guaranteed to happen before all dependencies between the v are exhausted. 2.7. The rational sieve and smoothness. A typical example is the rational sieve. In this factoring algorithm the factor base is selected to be P = {p : p is prime, p < B}, ap = (pmodn) (p e P), where B is a suitably chosen bound. Collecting relations between the ap is done as follows. Using a sieve, one searches for positive integers b with the property that both b and n + b are B-smooth, that is, have all their prime factors smaller than or equal to B. Replacing both sides in the congruence b = n + b mod n by their prime factorizations, we see that each such b gives rise to a multiplicative relation between the ap . The main merit of the resulting factoring algorithm—which is, essentially, the number field sieve, with the number field chosen to be the field of rational numbers—is that it illustrates the scheme above concisely. The rational sieve is not recommended for practical use, not because it is inefficient in itself, but because other methods are much faster. The choice of the "smoothness bound" B is very important: if B , and hence #P, is chosen too large, one needs to generate many relations, and one may end up with a matrix that is larger than one can handle in Step 3. On the other hand, if B is chosen too small, then not enough integers b will be found for which both b and n + b are ß-smooth. The same remarks apply to the other algorithms that satisfy our schematic description. In practice, the optimal value for B is determined empirically. In theory, one makes use of results that have been proved about the function i// defined by y/(x, y) = #{m e Z: 0 < m < x, m is y-smooth} ; so y/(x, y)/[x] is equal to the probability that a random positive integer < x has all its prime factors < y. Brief summaries of these results, which are 328 A. K. LENSTRA, H. W. LENSTRA, JR., M. S. MANASSE,AND J. M. POLLARD adequate for the purposes of factoring, can be found in [38, §2; 27, §2.A and (3.16)]. Not surprisingly, one finds that both from a practical and a theoretical point of view the optimal choice of the smoothness bound and the performance of the factoring algorithm depend mainly on the size of the numbers that one wishes to be smooth. The smaller these numbers are, the more likely are they to be smooth, the smaller the smoothness bound that can be taken, and the faster the algorithm. For a fuller discussion of this we refer to [10, §10]. In the rational sieve, one wishes the numbers b(n + b) to be smooth, and since b is small, these numbers may be expected to be a21+o(1)(for n —>oo). The theory of the i/7-function then suggests that the optimal choice for B is B = exp((v/2/2 + o(l))(log77)1''2(loglog77)1/2) (n -> oo), and that the running time of the entire algorithm is exp((\/2 + 0(l))(log7î)1</2(loglog77)1/2) (tî^oo). (This assumes that the dependencies in Step 3 are found by a method that is faster than Gaussian elimination.) 2.8. Other factoring algorithms. A big improvement is brought about by the continued fraction method [36] and by the quadratic sieve algorithm [38, 45], which belong to the same family. In these algorithms the numbers that one wishes to be smooth are only n'^+o'i) jn[s leads to the conjectured running time exp((l+o(l))(log77)l'/2(loglog7î)1/2) (77^00), the smoothness bound being approximately the square root of this. Although the quadratic sieve never had the honor of factoring a Fermât number, it is still considered to be the best practical algorithm for factoring numbers without small prime factors. In the number field sieve [28, 10], the numbers that one wishes to be smooth are tîo(1), or more precisely exp(0((log7i)2/3(loglog77)1/3)), and both the smoothness bound and the running time are conjecturally of the form exp(0((log«)1/3(loglog77)2''3)). This leads one to expect that the number field sieve is asymptotically the fastest factoring algorithm that is known. It remains to be tested whether for numbers in realistic ranges the number field sieve beats the quadratic sieve, if one does not restrict to special classes of numbers like Fermât numbers and Cunningham numbers. It is to be noted that the running time estimates that we just gave depend only on the number to be factored, and not on the size of the factor that is found. Thus, the quadratic sieve algorithm needs just as much time to find a small prime factor as to find a large one. There exist other factoring algorithms, not satisfying our schematic description, that are especially good at finding small THE FACTORIZATIONOF THE NINTH FERMAT NUMBER 329 prime factors of a number. These include trial division, Pollard's p± 1 method, Pollard's rho method, and the elliptic curve method (see [27, 31, 3, 34]). 3. The ninth Fermât number As we mentioned in §1, A. E. Western discovered in 1903 the factor 2424833 of 7*9, and Brillhart proved in 1967 that 7^/2424833 is composite. In this section we let n be the number 7*9/2424833, which has 148 decimal digits: n = 5529 373746539492451469451709955220061537996975706118 061624 681552 800446063738635599 565773930892108210210778 168305399196915314944498011438291393118209. We review the attempts that have been made to factor tí . We do not believe that the possibility of factoring n by means of the quadratic sieve algorithm was ever seriously considered. It would not have been beyond human resources, but it would have presented considerable financial and organizational difficulties. Several factoring algorithms that are good at finding small prime factors had been applied to 77. Richard Brent tried Pollard's p ± 1 method and a modified version of Pollard's rho method (see [27]), both without success. He estimates that if there had been a prime factor less than 1020, it would probably have been found by the rho method. The failure of the rho method is simply due to the size of the least prime factor P49 of n . The p ± 1 method would have been successful if at least one of the four numbers P49 ± 1, P99 ± 1 had been built from small prime factors. The failure of this method is explained by the factorizations P49- 1 = 2" . 19-47-82 488781 • 1143290228161321 •43 226490 359557706629, P49+ 1 = 2 • 3 • 167 982422 287027 •7397 205338652138126604651761 133609, P99- 1 =2" • 1129-26813-40 644377- 17 338437 577121 • 16975143302271 505426 897585 653131 126520 182328037821 729720833840 187223, P99+ 1 = 2 • 32 • 83 • 496412 357849 752879 199991393508659621 191392758432 074313189974107191710682399400 942498539967 666627. These factorizations were found by Richard Crandall with the p -1 method and the elliptic curve method. (He used a special second phase that he developed in collaboration with Joe Buhler, that is similar to the second phase given in [3].) Several people, including Richard Brent, Robert Silverman, Peter Montgomery, Sam Wagstaff, and ourselves, attempted to factor 77 using the elliptic curve method, supplemented with a second phase. Brent tried 5000 elliptic curves, his first-phase bound (i.e., the bound B\ from [34]) ranging from 240000 to 400000. This took 200 hours on a Fujitsu VP 100. Robert Silverman and Peter Montgomery tried 500 elliptic curves each, with a first-phase bound equal to 1 000000. We tried approximately 2000 elliptic curves, with 330 A. K. LENSTRA, H. W. LENSTRA, JR., M. S. MANASSE,AND J. M. POLLARD first-phase bounds ranging from 300000 to 1 000000, during a one-week run on a network of approximately 75 Firefly workstations at Digital Equipment Corporation Systems Research Center (DEC SRC). The elliptic curve method did not succeed in finding a factor. Our experience indicates that if there had been a prime factor less than 1030, it would almost certainly have been found. If there had been a factor less than 1040 we should probably have continued with the elliptic curve method. Our decision to stop was justified by the final factorization, which the elliptic curve method did not have a reasonable chance of finding without major technological or algorithmic improvements. The best published lower bound for the prime factors of n that had been rigorously established before n was completely factored is 247 « 1.4 >1014 (see [21, Table 2]). We have been informed by Robert Silverman that the work leading to [35] implied a lower bound 2048 • 1010, and that he later improved this to 2048 • 1012 . The best unpublished lower bound that we are aware of is 251« 2.25 • 1015, due to Gary Gostin (1987). If we had been certain—which we were not—that n had no prime factor less than 1030, then we would have known that 77 is a product of either two, three, or four prime factors. Among all composite numbers of 148 digits that have no prime factor less than 1030, about 15.8% are products of three primes, about 0.5% are products of four primes, and the others are products of two primes. We expected—rightly, as it turned out—to find two prime factors, but some of us would have been more excited with three large ones. 4. Algebraic number theory We factored 7*9by means of the number field sieve, which is a factoring algorithm that makes use of rings of algebraic integers. The number field sieve was introduced in [28] as a method for factoring Cunningham numbers. Meanwhile, a variant of the number field sieve has been invented that can, in principle, factor general numbers, but it has not yet proved to be of practical value (see [10]). In this section we review the basic properties of the ring Z[v/2], which is the ring that was used in the case of F9. A more general account of algebraic number theory can be found in [46], and for computational techniques we refer to [11]. 4.1. The number field Qiv^) and the norm map. The elements of the field Q(\f2) can be written uniquely as expressions ZUoQi^ > with Qi belonging to the field Q of rational numbers. For computational purposes we identify these elements with vectors consisting of five rational components <7o, q\ , qj, (?3, (?4, and addition and subtraction in the field are then just vector addition and subtraction. From the rule s[2 = 2 one readily deduces how elements of the field are to be multiplied. Explicitly, multiplying an element of the field by ß = Zi=o^'^ the matrix amounts to multiplying the corresponding column vector by / q0 2<?4 2tf3 2<72 2(7, \ q\ q0 2<74 2q3 2q2 q2 q\ q0 2q4 2q3 <?3 <?2 Q\ Qo 2(?4 V(?4 <73 <72 Q\ <7o/ . THE FACTORIZATIONOF THE NINTH FERMAT NUMBER 331 The norm N(ß) of ß is defined to be the determinant of this matrix, which is a rational number. Note that the norm can be written as a homogeneous fifth-degree polynomial in the q¡, with integer coefficients. We have N(ßy) = N(ß)N(y) forß,yeQ«/2), because the matrix belonging to ßy is the product of the two matrices belonging to ß and y . Applying this to y - ß~x , and using that N(l) — 1 , we find that N(ß) j- 0 whenever ß ¿ 0. The norm is one of the principal tools for studying the multiplicative structure of the field, and almost all that the number field sieve needs to know about multiplication is obtained from the norm map. In particular, for the purposes of the number field sieve no multiplication routine is needed. Below it will be useful to know that (4.2) N(a-by2~') = a5-2ib5 fora,bEQ, l</<4. One proves this by evaluating the determinant of the corresponding matrices. Division in the field can be done by means of linear algebra, since finding y¡ß is the same as solving the equation ß • x = y, which can be written as a system of five linear equations in five unknowns. There exist better methods, but we do not discuss these, since the number field sieve needs division just as little as it needs multiplication. 4.3. The number ring Z[v/2] and smoothness. The elements ZUori^ °f QXv^) for which all r¡ belong to Z form a subring, which is denoted by Z[\fï\. If ß belongs to Z[v^], then the matrix associated with ß has integer entries, so its determinant N(ß) belongs to Z. If B is a positive real number, then a nonzero element ß of Z\sf2\ will be called B-smooth if the absolute value \N(ß)\ of its norm is 5-smooth in the sense of §2.7. We note that \N{ß)\ can be interpreted as the index of the subgroup ßZ\\/2\ = {ßy: y e Zfv^]} of Z[^2]: (4.4) \N(ß)\^#(Z[^2]/ßZ[^2]) for ß e Zfv^], ß?0. This follows from the following well-known lemma in linear algebra: // A is a k x k matrix with integer entries and nonzero determinant, and we view A as a map Zk —>Zk , then the index of AZk in Zk is finite and equal to \at\A\. 4.5. Ring homomorphisms. We will need to know a little about ring homomorphisms defined on Ztv^]. Let 7? be a commutative ring with 1. If y. Zfv^] —► 7? is a ring homomorphism, then the element c = y/{\f2) of 7? clearly satisfies c5 = 2, where 2 now denotes the element 1 + 1 of R. Con- versely, if c E R satisfies c5 = 2, then there is a unique ring homomorphism y/\ Z[v/2] -» 7? satisfying y/{\/2) - c, namely the map defined by hÍ>^') \/=0 =¿>'' / (nez); i=0 here the r, on the right are interpreted as elements of R , just as we put 2=1 + 1 above. We conclude that giving a ring homomorphism from Z\\f2\ to R is the same as giving an element c of R that satisfies c5 = 2 . 332 A. K. LENSTRA, H. W. LENSTRA, JR., M. S. MANASSE,AND J. M. POLLARD Example. Let tj = (2512+1)/2424833, and put R = Z/nZ and