Associated Topics || Dr. Math Home || Search Dr. Math

### Factoring Algorithms

```Date: 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
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
sieve.  The quadratic sieve works well for very large numbers, but
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

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):

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

"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.

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.
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search