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). 
If we instead start with x(0) = 1033994, the factor of 131 appears on 
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/