Factorization of Fermat Numbers^{∗}

Richard P. Brent Computer Sciences Laboratory Australian National University

         rpb@cslab.anu.edu.au

∗Presented at 40th Australian Mathematical Society Conference, Flinders University, 9 July 1996. Copyright \begin{matrix}c \\ ◯ \end{matrix}1996, R. P. Brent. rpb161t typeset using L^{A}TEX

Abstract

This talk gives a brief historical summary of attempts to factor Fermat numbers, and describes the complete factorization of the tenth Fermat number, 2^{1024} + 1. This number is a product of four prime factors with 8, 10, 40 and 252 decimal digits. The 40-digit factor was found by the elliptic curve method after about 140 Mflop-years of computation.

Outline

• Some history.

• The elliptic curve method (ECM).

• Factorization of F_{10}.

Notation

p_{n} denotes a prime number with n decimal digits, e.g. p_{3} = 163. Similarly, c_{n} denotes a composite number with n decimal digits, e.g. c_{4} = 1729.

Testing Compositeness

To show that N is composite, it is sufficient to find a “witness” a ∈ (1, N) such that

a^{N−1} ≠ 1 mod N .

Then Fermat’s “little” theorem says that N is composite, although we may not know a nontrivial factor of N.

Some History

For a nonnegative integer n, the n-th Fermat number is F_{n} = 2^{2^{n}} + 1. It is known that F_{n} is prime for 0 ≤ n ≤ 4, and composite for 5 ≤ n ≤ 23. Also, for n ≥ 2, the factors of F_{n} are of the form

k2^{n+2} + 1 .

In 1732 Euler found that 641 = 5 · 2^{7} + 1 is a factor of F_{5}, thus disproving Fermat’s belief that all F_{n} are prime. Euler apparently used trial division by primes of the form 64k + 1 (not just 128k + 1).

The complete factorization of the Fermat numbers F_{6}, F_{7}, … has been a challenge since Euler’s time. Because the F_{n} grow rapidly in size, a method which factors F_{n} may be inadequate for F_{n+1}.

No Fermat primes larger than F_{4} are known, and a probabilistic argument makes it plausible that only a finite number of F_{n} (perhaps only F_{0}, …, F_{4}) are prime. It is known that F_{n} is composite for 5 ≤ n ≤ 23.

F_{6}

In 1880, Landry factored F_{6} = 274177 · p_{14} . Landry’s method was never published in full, but Williams has attempted to reconstruct it.

Hand Computations

In the period 1877–1970, several small factors of F_{n} for various n ≥ 9 were found by taking advantage of the special form of these factors. For example, in 1903 Western found the factor p_{7} = 2424833 = 37 · 2^{16} + 1 of F_{9}.

Significant further progress was only possible with the development of the digital computer and more efficient algorithms.

In 1970, Morrison and Brillhart factored

F_{7} = 59649589127497217 · p_{22}

by the continued fraction method. This method has now been superseded by the multiple-polynomial quadratic sieve (MPQS) method which, surprisingly, has never been the first to factor a Fermat number.

In 1980, Brent and Pollard factored

F_{8} = 1238926361552897 · p_{62}

by a modification of Pollard’s “rho” method. The “rho” method is now largely superseded by Lenstra’s elliptic curve method (ECM), of which more later.

The larger factor p_{62} of F_{8} was first proved prime by Williams using the method of Williams and Judd. Later, I provided a simpler proof by factoring p_{62} − 1.

Nowadays, F_{7} and F_{8} are “easy” to factor by ECM or MPQS.

Logically, the next step after the factorization of F_{8} was the factorization of F_{9}. It was known that

F_{9} = 2424833 · c_{148}

The 148-digit composite number resisted attack by methods such as Pollard rho, Pollard p ± 1, and the elliptic curve method (ECM), which would have found “small” factors. It was too large to factor by the continued fraction method or even by MPQS.

The difficulty was finally overcome by the invention of the (special) number field sieve (SNFS), based on a new idea of Pollard. In 1990, Lenstra, Lenstra, Manasse and Pollard, with the assistance of many collaborators and approximately 700 workstations scattered around the world (including Australia) completely factored F_{9} by SNFS.

F_{9} = 2424833 · p_{49} · p_{99} ,
p_{49} = 7455602825647884208337395736200454918783366342657

F_{10} has been a “most wanted” number in various lists of composite numbers since the factorization of F_{9} in 1990.

F_{10} was proved composite in 1952 by Robinson, using Pépin’s test on the SWAC. A small factor, 45592577, was found by Selfridge in 1953 (also on the SWAC). Another small factor, 6487031809, was found by Brillhart in 1962 on an IBM 704. Brillhart later found that the cofactor was a 291-digit composite.

Using ECM we found a 40-digit factor of F_{10} on October 20, 1995. The 252-digit cofactor c_{291}/p_{40} passed a probabilistic primality test and was soon proved to be prime using the method of Atkin and Morain (based, appropriately, on elliptic curves). Thus, the complete factorization of F_{10} is

F_{10} = 45592577 · 6487031809 · p_{40} · p_{252} ,
p_{40} = 4659775785220018543264560743076778192897

F_{11} was completely factored in 1988, before the factorization of F_{9} and F_{10}. In fact,

F_{11} = 319489 · 974849 ·
167988556341760475137 ·
3560841906445833920513 · p_{564}

The two 6-digit factors were found by Cunningham in 1899, and I found the remaining factors in May 1988, using ECM on a Fujitsu VP100. The 564-digit factor passed a probabilistic primality test, and a rigorous proof of primality was provided by Morain.

The reason why F_{11} could be completely factored before F_{9} and F_{10} is that the difficulty of completely factoring numbers by ECM is determined mainly by the size of the second-largest prime factor of the number.

The second-largest prime factor of F_{11} has 22 digits and is much easier to find by ECM than the 40-digit factor of F_{10} or the 49-digit factor of F_{9}.

Summary

A brief summary of the history of factorization of F_{5}, …, F_{11} is given in the Table.

Table 1: Complete factorization of F_{n}, n = 5, …, 11

n  Factorization  Date  Comments
5  p_{3} · p_{7}  1732  Euler
6  p_{6} · p_{14}  1880  Landry
7  p_{17} · p_{22}  1970  Morrison and Brillhart
8  p_{16} · p_{62}  1980  Brent and Pollard (p_{16}, p_{62})
1980  Williams (primality of p_{62})
9 p_{7} · p_{49} · p_{99} 1903 Western (p_{7})
1990  Lenstra et al (p_{49}, p_{99})
10 p_{8} · p_{10} · p_{40} · p_{252} 1953 Selfridge (p_{8})
1962  Brillhart (p_{10})
1995  Brent (p_{40}, p_{252})
11 p_{6} · p′_{6} · p_{21} · p_{22} · p_{564} 1899 Cunningham (p_{6}, p′_{6})
1988  Brent (p_{21}, p_{22}, p_{564})
1988  Morain (primality of p_{564})

The smallest Fermat number which is not yet completely factored is F_{12}. It is known that

F_{12} = 114689 · 26017793 ·
63766529 · 190274191361 ·
1256132134125569 · c_{1187} ,

where the 16-digit factor was found by Baillie in 1986, using the Pollard p − 1 method (and rediscovered in 1988 using ECM).

F_{12} has at least seven prime factors, spoiling a “conjecture” based on the observation that F_{n} has exactly n − 6 prime factors for 8 ≤ n ≤ 11.

It is known that

F_{13} = 2710954639361 ·
2663848877152141313 ·
3603109844542291969 ·

319546020820551643220672513 · c_{2391} ,

where the 13-digit factor was found by Hallyburton and Brillhart (1975), the two 19-digit factors were found by Crandall (1991).

I found the 27-digit factor in June 1995, using ECM on an IBM PC equipped with a Dubner Cruncher board.

F_{14}

F_{14} = c_{4933} is composite, but no nontrivial factors are known.

A Brief Description of ECM

The elliptic curve method (ECM) was discovered by H. W. Lenstra, Jr. in 1985. Various practical refinements were suggested by Montgomery, Suyama, and others. References can be found in my report [4].

Lenstra’s key idea was to apply Pollard’s “p − 1” method but to work over a different group G. If the method fails, another group can be tried. This is not possible for the p − 1 method, because it uses a fixed group.

ECM uses groups defined by pseudo-random elliptic curves over F_{p}, where p > 3 is the prime factor we hope to find. (Fortunately, we don’t need to know p in advance.) By a theorem of Hasse (1934), the group order g for an elliptic curve over F_{p} satisfies

|g − p − 1| < 2\sqrt{p} .

By a result of Deuring, all g satisfying this inequality are possible.

Lenstra’s Analysis of ECM

Consider applying ECM to a composite integer N with smallest prime factor p. Modulo an unproved but plausible assumption regarding the distribution of prime factors of random integers in “short” intervals, Lenstra showed that ECM will find p in an expected number

W (p) = exp (\sqrt{(2 + o(1)) log p log log p})

of multiplications (mod N), where the “o(1)” term tends to zero as p → ∞.

ECM can “routinely” find factor up to about 30 decimal digits, and it has successfully found factors p as large as 47 decimal digits. Details can be found in [3].

Choice of Parameters

ECM has several parameters. The most important is the first-phase limit B_{1}. The optimal choice of the parameters depends on the size of the factor p. Since p is unknown, we have to guess or use some sort of adaptive strategy. Fortunately, the expected performance of ECM is not very sensitive to the choice of parameters.

Expected Performance of ECM

In Table 2 we give a small table of log_{10} W for factors of D decimal digits. The precise figures depend on assumptions about the implementation, see [4].

Table 2: Expected work for ECM

digits D log_{10} W
20  7.35
30  9.57
40  11.49
50  13.22
60  14.80

Factorization of F_{10}

ECM was implemented on a Fujitsu VP100 in March 1988. The program was soon successful in completing the factorisation of F_{11}, but had no success with other Fermat numbers, apart from rediscovering known factors. The VP100 was upgraded to a VP2200 in 1991.

In September 1994 we started running a similar program on one or two 60 Mhz SuperSparc processors. In July 1995 six more 60 Mhz SuperSparc processors became available for a limited period. We attempted to factor F_{10} on all eight SuperSparcs.

The p_{40} factor of F_{10} was found by a run which started on Oct 14 and finished on Oct 20, 1995. The run tried 10 curves with B_{1} = 2000000 in about 114 hours of CPU time.

Summary of F_{10} runs

In Table 3, F is an estimate of the expected number of times that the factor p_{40} should be found with the given B_{1} and number of curves. E is an estimate of the efficiency compared to the optimal choice of B_{1} ≃ 3400000. The last row of the table gives totals (for number of curves and F) and weighted means (for B_{1} and E).

Table 3: ECM runs on F_{10}

B_{1}  curves  F  E  machine(s) and dates
6 × 10^{4}  2000  0.0010  0.14  VP100, Mar 1988 – Nov 1990
2 × 10^{5}  17360  0.0910  0.42  VP2200, Aug 1991 – Aug 1995
5 × 10^{5}  700  0.0152  0.69  Sparc × 2, Sep 1994 – Jul 1995
10^{6}  480  0.0262  0.87  Sparc × 8, Jul 1995 – Aug 1995
2 × 10^{6}  900  0.1100  0.98  Sparc × 8, Aug 1995 – Oct 1995
2.9 × 10^{5}  21440  0.2434  0.63

The Computational Work

Each curve on a 60 Mhz SuperSparc takes about 5.7 × 10^{−6}B_{1} hours of CPU time. If a 60 Mhz SuperSparc is counted as a 60-Mips machine, then our computation took about 240 Mips-years. This is comparable to the 340 Mips-years estimated for sieving to factor F_{9} by SNFS. (SNFS has since been improved, so the 340 Mips-years could now be reduced by an order of magnitude.) A 130-digit number, RSA130, took 500 Mips-years by GNFS (May 1996).

Since the inner loops of our programs use floating-point arithmetic, Mflops are a more appropriate measure than Mips. The VP2200/10 is rated at 1250 Mflop (peak performance). If our factorization of F_{10} had been performed entirely on the VP2200, it would have taken about 6 weeks of machine time, or 140 Mflop-years. Cryptographers should note that this amounts to about 75 minutes on a 1 Teraflop machine.

Multiplications

The number of multiplications (mod N) is a machine-independent measure of the work to factor N. Each curve takes about 22.9 B_{1} such multiplications.

Overall, our factorization of F_{10} took 1.4 × 10^{11} multiplications (mod N), where N = c_{291}. Table 2 predicts 3.3 × 10^{11} with the optimal choice of parameters.

Numbers mod c_{291} were represented with 38 digits and base 2^{26} (on the VP100/VP2200) or with 41 digits and base 2^{24} (on the Sparc), so each multiplication (mod N) took more than 10^{4} floating-point operations.

The Group Order

The successful elliptic curve leading to the factorization of F_{10} had order

g = p_{40} + 1 − 3674872259129499038
= 2^{2} · 3^{2} · 5 · 149 · 163 · 197 · 7187 ·

18311 · 123677 · 226133 · 314263 · 4677853 .

The probability that a random integer near g/12 has largest prime factor at most 4677853 and second-largest prime factor at most 314263 is about 5.8 × 10^{−6}. The phase 1 limit for the successful run was B_{1} = 2 × 10^{6}, but our program finds p_{40} with B_{1} as small as 314263 if the same curve and starting point are used. (The largest factor 4677853 of g is caught by “phase 2” of ECM.)

Acknowledgements

Thanks are due to the ANU Supercomputer Facility and to many people, including: John Brillhart, Richard Crandall, Bruce Dodson, Harvey Dubner, Wilfrid Keller, Donald Knuth, Arjen Lenstra, Hendrik Lenstra, Jr., Peter Montgomery, François Morain, John Pollard, John Selfridge, Daniel Shanks Robert Silverman, Hiromi Suyama, Sam Wagstaff, Jr.

References

[1] A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29–68. Programs available from ftp://

ftp.inria.fr/INRIA/ecpp.V3.4.1.tar.Z .

[2] R. P. Brent, Factorization of the eleventh Fermat number (preliminary report), AMS Abstracts 10 (1989), 89T-11-73.

[3] R. P. Brent, Large factors found by ECM, Computer Sciences Laboratory, Australian National University, Dec. 1995 (and more

recent updates). ftp://nimbus.anu.edu.au/
pub/Brent/champs.ecm .

[4] R. P. Brent, Factorization of the tenth and eleventh Fermat numbers, Report TR-CS-96-02, Computer Sciences Laboratory, Australian National University, Feb. 1996, 25 pp.

ftp://nimbus.anu.edu.au:/pub/Brent/
rpb161tr.dvi.Z .

[5] R. P. Brent and J. M. Pollard, Factorization of the eighth Fermat number, Math. Comp. 36 (1981), 627-630.

[6] J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of b^{n} ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers, 2nd ed., Amer. Math. Soc., Providence, RI, 1988.

[7] C. Caldwell, The Dubner PC Cruncher – a microcomputer coprocessor card for doing integer arithmetic, review in J. Rec. Math. 25(1), 1993.

[8] D. V. and G. V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Adv. in Appl. Math. 7 (1986), 187–237.

[9] L. Euler, Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus, Comm. Acad. Sci. Petropol. 6, ad annos 1732–33 (1738), 103–107; Leonhardi Euleri Opera Omnia, Ser. I, vol. II, Teubner, Leipzig, 1915, 1–5.

[10] F. Landry, Note sur la décomposition du nombre 2^{64} + 1 (Extrait), C. R. Acad. Sci. Paris 91 (1880), 138.

[11] A. K. Lenstra and H. W. Lenstra, Jr. (editors), The development of the number field sieve, Lecture Notes in Mathematics 1554, Springer-Verlag, Berlin, 1993.

[12] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The factorization of the ninth Fermat number, Math. Comp. 61 (1993), 319–349.

[13] H. W. Lenstra, Jr., Factoring integers with elliptic curves, Annals of Mathematics (2) 126 (1987), 649–673.

[14] P. L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), 243–264.

[15] P. L. Montgomery, An FFT extension of the elliptic curve method of factorization, Ph. D. dissertation, Mathematics, University of California at Los Angeles, 1992.

[16] M. A. Morrison and J. Brillhart, A method of factorization and the factorization of F_{7}, Math. Comp. 29 (1975), 183–205.

[17] A. M. Vershik, The asymptotic distribution of factorizations of natural numbers into prime divisors, Dokl. Akad. Nauk SSSR 289 (1986), 269–272; English transl. in Soviet Math. Dokl. 34 (1987), 57–61.

[18] H. C. Williams, How was F_{6} factored?, Math. Comp. 61 (1993), 463–474.