LECTURE 6

Integer factorisation, elliptic curves and Fermat numbers

This lecture will compare several integer factorization algorithms, including Lenstra's elliptic curve method (ECM), the multiple polynomial quadratic sieve (MPQS), and the number field sieve (NFS), for the application of factoring ``typical'' or ``random'' large integers. We will conclude by giving a brief historical summary of attempts to factor Fermat numbers, and give some details of the recent factorisation of the tenth Fermat number.

Related lecture

• Integer factorisation algorithms illustrated by the factorisation of Fermat numbers.

Background

• H. W. Lenstra, Jr., Factoring integers with elliptic curves, Annals of Mathematics (2) 126 (1987), 649-673. (The original paper on ECM.)
• H. Riesel, Prime numbers and computer methods for factorization, 2nd edition, Birkhauser, Boston, 1994. (A good introductory book.)

Bibliography and relevant links

• R. P. Brent, Some integer factorization algorithms using elliptic curves, Australian Computer Science Communications 8 (1986), 149-163. (One of the first papers on ECM, including an analysis of the birthday paradox second phase.)
• R. P. Brent, Factorization of the tenth Fermat numbers, Mathematics of Computation 68 (1999), 429-451. (Includes a description of the implementation of ECM and many references.)
• R. P. Brent, R. E. Crandall, K. Dilcher and C. van Halewyn, Three new factors of Fermat numbers, Mathematics of Computation, to appear. (Describes some recent ECM successes.)
• R. P. Brent, Some parallel algorithms for integer factorization, Proceedings Euro-Par'99, to appear. (A recent survey with a large bibliography.)
• R. P. Brent and J. M. Pollard, Factorization of the eighth Fermat number, Mathematics of Computation 36 (1981), 627-630. (A lot of progress has been made since 1981!)
• P. L. Montgomery, A survey of modern integer factorization algorithms, CWI Quarterly 7 (1994), 337-366. (A good survey, including ECM and NFS.)
• P. L. Montgomery, An FFT extension of the elliptic curve method of factorization, Ph. D. dissertation, Mathematics, University of California at Los Angeles, 1992. (For many refinements to Lenstra's basic method.)
• Large factors found by ECM. ("Large" currently means at least 47 decimal digits.)

Compressed postscript file of the transparencies used in the lecture

Return to first lecture

Return to list of special lectures on algorithms