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

### Factoring Large Numbers

```
Date: 10/26/98 at 02:24:40
From: Matt McGrew
Subject: Large Number Factoring

I am working on a project, and I need to factor extremely large
numbers, on the order of hundreds of digits, specifically to find the
largest factor. Regardless of the implementation in a program for
doing this, my question is for you to confirm that my current method is
the "quickest" (barring any extremely complicated math).

Say we have N = 2211280 (a SMALL example). What I am doing is trying
every prime number, X, in the range from 2 to sqrt(N), and the highest
prime I find that satisfies N mod X = 0 in that range is the greatest
factor for N. In this case I get, the numbers 2, 5, 131, 211, and
X = 211 is the number I am looking for. Is this the quickest method
for factoring a number (assuming I can find primes fast, which I can)?

Unfortunately using this method for numbers hundreds of digits long
requires excess time processing the billions and billions of primes
from 2 to sqrt(N). Thank you.
```

```
Date: 10/26/98 at 16:09:13
From: Doctor Rob
Subject: Re: Large Number Factoring

Matt,

You are faced with a traditionally hard problem. For numbers with
hundreds of digits, there is no good way to do what you want.

Here is a better way, but still hopeless for really big numbers. It is
called the Pollard Rho Factoring Algorithm.

Suppose the number to be factored is N, and you have tested it and
found that it is composite. Pick a random start x(0) with
1 < x(0) < N. For i = 1, 2, 3, ..., compute:

x(i) = x(i-1)^2 - 1 (mod N)
x(2*i-1) = x(2*i-2)^2 - 1 (mod N)
x(2*i) = x(2*i-1)^2 - 1 (mod N)
d(i) = GCD(N, x[2*i]-x[i])

If d(i) = 1, increment i and repeat the computation.
If 1 < d(i) < N, then you have split N into two factors:
N = d(i)*[N/d(i)].
If d(i) = N, pick a new value of x(0) and begin the process anew.

Once you have split N into two parts, you have to test them both to
see if they are prime or composite, and repeat the process on the
composite parts.

Example: N = 1037. Pick the random start x(0) = 44.

i       x(i)         x(2*i)         d(i)
0        44            44            --
1       898           654            61

and, sure enough, N = 61*17, and both factors are prime.

With your example N = 2211280 and the start x(0) = 12843, 5 would
appear as a factor after 1 step, 16 after 2 steps, and 211 after 13
steps, leaving 131 (which would have appeared at the 14th step).
the first step, and on the second step, we get 40*422, both parts
composite.

Usually to find a factor P takes about sqrt(P) steps. We were lucky in
the first example, needing only one step. With your method, it takes
P/ln(P) steps, and luck plays no part. Pollard Rho steps are more
complicated than your divisions, however. The explanation for why this
works is not within the scope of this note, but involves some
fascinating ideas from number theory and probability theory.

While this method is better than dividing by the primes up to sqrt(N),
it still usually fails for some values of N with 50 or more digits.
To do better still requires more complicated methods, which go by the
names of the P-1 Factoring Algorithm, the P+1 Factoring Algorithm, the
Continued Fraction Factoring Algorithm, the Quadratic Sieve Factoring
Algorithm, and the Number Field Sieve Factoring Algorithm.

The record for even the most sophisticated of these algorithms in
trying to factor hard numbers is 130 decimal digits, and this took a
legion of computers working in parallel many months to factor.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Algorithms
College Number Theory
High School 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