Factoring AlgorithmsDate: 08/11/2004 at 13:38:56 From: Kusa Subject: How can I factorize a long number? I'm wondering if there is any sort of algorithm for taking a very large number and factoring it? Date: 08/11/2004 at 16:39:13 From: Doctor Vogler Subject: Re: How can I factorize a long number? Hi Kusa, Thanks for writing to Dr Math. Yes, there are many different algorithms for factoring a large number, some of which are better suited to certain sizes of numbers. A few of them include the following: Trial division Pollard Rho Pollard p-1 (that's p minus one) Elliptic Curve Factoring Method Dixon's Algorithm Quadratic Sieve Number Field Sieve Trial division is just dividing by all of the primes up to the square root of the number and is the best algorithm for very small numbers, but is terrible for large numbers. Pollard rho and Pollard p-1 are very nice for fairly small numbers and only a few larger numbers. The elliptic curve method is starting to get a little more complicated, but it works better on numbers a little larger. Dixon's Algorithm isn't very efficient, but it will help you to understand the quadratic sieve. The quadratic sieve works well for very large numbers, but it's a little complicated. It will, however, help you to understand the number field sieve. The number field sieve is extremely complicated, but it is the best known algorithm for the largest numbers we can factor. Now search for these on the internet, or look for a book on factoring to learn the details of all of these algorithms. Also, I did some searching a while ago and found several web sites that talk about various factoring algorithms. You might find any of the following links useful. Another person's opinion or statements about the state-of-the-art in factoring algorithms: http://www.x5.net/faqs/crypto/q48.html From our archives, the asker describes trial division, and the math doctor describes the Pollard rho algorithm: Factoring Large Numbers http://mathforum.org/library/drmath/view/51544.html A description of the Pollard p-1 algorithm, with a brief introduction to the Elliptic Curve Method (ECM): http://home.netcom.com/~jrhowell/math/ecm.htm A collection of many algorithms (but some very brief or missing descriptions): http://www.frenchfries.net/paul/factoring/theory/ Notes from a class at MIT: http://www-math.mit.edu/18.310/ Pay special attention to chapter 21 (where Pollard rho is called "tortoise and hare"): http://www-math.mit.edu/18.310/Factoring_numbers.html http://www-math.mit.edu/18.310/21.-Factoring-Numbers-1.pdf and chapter 22 (about ECM): http://www-math.mit.edu/18.310/Elliptic_curves.html http://www-math.mit.edu/18.310/22.-Factoring-II-Elliptic-Curves.pdf From our archives, a summary with references to good text books: Public Key Cryptography http://mathforum.org/library/drmath/view/51531.html MathWorld's brief description of the Quadratic Sieve (QS): Quadratic Sieve http://mathworld.wolfram.com/QuadraticSieve.html A description of Quadratic Sieve: http://www.math.uiuc.edu/~landquis/quadsieve.pdf A paper by Carl Pomerance on Quadratic Sieve: http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/E84/169.PDF From our archives, a one-page overview of the Number Field Sieve (NFS): Factorization Algorithms http://mathforum.org/library/drmath/view/51548.html Another brief description of NFS: http://www.fact-index.com/g/ge/general_number_field_sieve.html A long and detailed Master's Thesis on NFS (probably easier reading): http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf A (dense) pdf on NFS: http://www.std.org/~msm/common/nfspaper.pdf Links to papers about NFS: http://triade.studentenweb.org/Nfs/nfs.html "Factor World" - A web site about factoring: http://www.crypto-world.com/FactorWorld.html including gzipped papers on ECM, QS, NFS: http://www.crypto-world.com/FactorPapers.html and some implementations (program code): http://www.crypto-world.com/FactorCode.html Links to current internet factoring projects on mersenne.org: http://www.mersenne.org/ecm.htm I hope you find these useful. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 08/13/2004 at 02:17:20 From: Kusa Subject: Thank you (How can I factorize a long number?) Thank you for your great response! This is very helpful. You provide a great service. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/