Factoring Papers

Note: many of these papers come from other web sites. If the location of the paper is not mentioned, then it is stored at our web site.

Surveys

• A Survey of Modern Integer Factorization Algorithms by Peter L. Montgomery from CiteSeer.
• Some Parallel Algorithms for Integer Factorization by Richard Brent (zipped, postscript, 107K) from Richard Brent's homepage (ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/rpb193.ps.gz).
• Integer Factoring by Arjen lenstra (pdf, 139K) from http://modular.fas.harvard.edu/edu/Fall2001/124/misc/arjen_lenstra_factoring.pdf.
• A Tale of Two Sieves by Carl Pomerance (pdf, 268K) from http://www.ams.org/notices/199612/pomerance.pdf.

Elliptic Curve method

• Vectorization of the Elliptic Curve Method by Peter L. Montgomery (zipped, postscript, 102K) from CWI (ftp://ftp.cwi.nl:/pub/pmontgom).
• An FFT Extension of the Elliptic Curve Method of Factorization by Peter L. Montgomery (zipped, postscript, 102K) from CWI (ftp://ftp.cwi.nl:/pub/pmontgom).
• Some Integer Factorization Algorithms using Elliptic Curves by Richard Brent (zipped, postscript, 90K) from Richard Brent's homepage (ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/rpb102.ps.gz).
• Factorization of the Tenth Fermat Number by Richard Brent (zipped, postscript, 117K) from Richard Brent's homepage.
• Three New Factors of Fermat Numbers by R. Brent, R. Crandall, K. Dilcher and C. Van Halewyn (zipped, pdf, 61K) from Richard Brent's homepage (ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/rpb175.ps.gz).

Quadratic Sieve

• Factoring Integers with Large Prime Variations of the Quadratic Sieve by H. Boender and H.J.J. te Riele (compressed postscript, 109K) from CWI (http://www.cwi.nl/ftp/CWIreports/NW/NM-R9513.ps.Z).
• Factoring Integers with the Self-Initializing Quadratic Sieve by S. Contini (zipped, postscript, 113K).

Number Field Sieve

• The Factorization of the Ninth Fermat Number by A.K. Lenstra, H.W. Lenstra, M.S. Manasse, and J.M. Pollard (postscript, 230K) from Mark Manasse's homepage (http://www.std.org/~msm/common/f9paper.ps).
• The Number Field Sieve by A.K. Lenstra, H.W. Lenstra, M.S. Manasse, and J.M. Pollard (postscript, 160K) from Mark Manasse's homepage (http://www.std.org/~msm/common/nfspaper.ps).
• On Quadratic Polynomials for the Number Field Sieve by Brian Murphy and Richard Brent (zipped, postscript, 93K) from Richard Brent's homepage (ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/rpb178.ps.gz).
• Factorization of RSA-140 Using the Number Field Sieve by S. Cavallar, B. Dodson, A.K. Lenstra, P.C. Leyland, W.M. Lioen, P.L. Montgomery, B. Murphy, H.J.J. te Riele, and P. Zimmermann (Compressed postscript, 557K) from CWI (http://www.cwi.nl/ftp/CWIreports/MAS/MAS-R9925.ps.Z).
• Factorization of a 512-bit RSA Modulus by S. Cavallar, B. Dodson, A.K. Lenstra, W.M. Lioen, P.L. Montgomery, B. Murphy, H.J.J. te Riele, K. Aardal, J. Gilchrist, G. Guillerm, P. Leyland, J. Marchand, F. Morain, A. Muffet, Chris Putnam, Craig Putnam, and Paul Zimmermann. (compressed postscript, 130K) from CWI (http://www.cwi.nl/ftp/CWIreports/MAS/MAS-R0007.ps.Z).
• Polynomial selection for the number field sieve integer factorisation algorithm by B. Murphy (compressed postscript, 816K) from http://web.comlab.ox.ac.uk/oucl/work/richard.brent/ftp/Murphy-thesis.ps.gz.
• An Introduction to the General Number Field Sieve by Matthew Briggs (pdf, 850K) from http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf.
• Factoring estimates for a 1024-bit RSA modulus by Arjen K. Lenstra, Eran Tromer, Adi Shamir, Wil Kortsmit, Bruce Dodson, James Hughes, Paul Leyland. Available at Eran Tromer's web site.
• On the cost of factoring RSA-1024 by Adi Shamir and Eran Tromer. Available at Eran Tromer's web site.
• GNFS Factoring Statistics of RSA-100, 110, ..., 150 by Kazumaro Aoki, Yuji Kida, Takeshi Shimoyama, and Hiroki Ueda. Available on the crypto eprint archive.
• A Kilobit Special Number Field Sieve Factorization by Kazumaro Aoki, Jens Franke, Thorsten Kleinjung, Arjen Lenstra and Dag Arne Osvik. Available on the crypto eprint archive.

Square roots in number fields

• Square Roots of Products of Algebraic Numbers by Peter L. Montgomery (zipped, postscript, 118K) from CWI (ftp://ftp.cwi.nl:/pub/pmontgom).
• A Montgomery-Like Square Root for the Number Field Sieve by Phong Nguyen from CiteSeer.

Linear algebra

• Solving Large Sparse Linear Systems over Finite Fields by B. A. LaMacchia and A. M. Odlyzko from CiteSeer.
• A Block Lanczos Algorithm for Finding Dependencies over GF(2) by Peter L. Montgomery (zipped, postscript, 221K) from CWI (ftp://ftp.cwi.nl:/pub/pmontgom).

Other factoring algorithms

• Factorization of the Eighth Fermat Number by Richard Brent and John Pollard, from Richard Brent's homepage (http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub061.html).
• Using Lucas Sequences to Factor Large Integers Near Group Orders by ZHANG Zhenxiang (postscript, 334K).

Miscellaneous factoring papers

• The Future of Integer Factorization by A.M. Odlyzko (pdf, 140K) from Andrew Odlyzko's homepage (hhttp://www.dtc.umn.edu/~odlyzko/doc/future.of.factoring.pdf).
• On the Complexity of Computing Discrete Logarithms and Factoring Integers by A.M. Odlyzko (pdf, 9K) from Andrew Odlyzko's homepage (http://www.dtc.umn.edu/~odlyzko/doc/arch/factoring.logs.pdf).

Other relevant papers

• Discrete Logarithms in Finite Fields and their Cryptographic Significance by A.M. Odlyzko (pdf, 212K) from Andrew Odlyzko's homepage (http://www.dtc.umn.edu/~odlyzko/doc/arch/discrete.logs.pdf).
• Selecting Cryptographic Key Sizes by A.K. Lenstra and E. Verheul CitSeer.

Return to the FactorWorld main page.

Include a paper on FactorWorld. You may either email a link to your paper, or email the paper itself to FactorWorld. However, please be sure that no copyright laws are being violated.