Factoring Very Large Numbers into Primes

Date: 12/05/2003 at 00:05:53
From: Chetan
Subject: finding the factors of any given number

Suppose I have a really big number to be factored into primes.  What 
is the best possible way of doing it?  I know I can divide by 
increasing primes, but that ges very hard for monstrous numbers.  Is
it possible to find them in any other way?

Date: 12/05/2003 at 17:14:42
From: Doctor Rob
Subject: Re: finding the factors of any given number

Thanks for writing to Ask Dr. Math, Chetan!

There are a number of ways to approach finding prime factors of large
natural numbers.  I will discuss several, including some that are
based in a field of mathematics called modular arithmetic.

The one you know, where you divide successively by 2, 3, 5, 7, 11, 13, 
17, 19, 23, ..., the prime numbers in order, is called Trial Division.  
It is very effective for numbers up to about 1000 when doing the 
divisions by hand, and to about 1,000,000 when using a computer.  The 
worst-case time to factor a composite N is sqrt(N) divisions.  The 
smallest prime factor is always found first.

An old-fashioned way which is often effective is to express N as
the difference of two squares, that is, to find x and y such that
N = x^2 - y^2 = (x - y)*(x + y).  One way to do this is to start with
x being the integer just larger than sqrt(N), and see if x^2 - N is
or is not a perfect square.  If it is, you have found y^2.  If it
is not, replace x by x + 1, and try again.  There are some shortcuts
which you'll soon discover, since (for example) perfect squares
must end in 00, n1, n4, 25, m6, or n9, where n is an even digit and
m is an odd one.  Even better, one can eliminate whole congruence
classes of possible values of x by reducing the equation modulo a
small prime, and using the fact that both x^2 and y^2 must be 
quadratic residues modulo that prime.

For example, suppose N = 1189.  Then start with x = 35, x^2 - N =
1225 - 1189 = 36 = 6^2.  We've been lucky and got a success on the
very first value of x!  Then N = (35 - 6)*(35 + 6) = 29*41.

Another interesting way is to express N as the SUM of two squares in 
two different ways:

   N = a^2 + b^2 = c^2 + d^2, 0 < a < c < d < b.

This can only work if N = 1 (mod 4).  Then

   N = (b*c + a*d)*(b*c - a*d)/(b + d)*(b - d).

The factors in the denominator will cancel with some in the numerator, 
but what is left will still be a useful factorization of N into two 
parts.

Again, if N = 1189, one can find 1189 = 10^2 + 33^2 = 17^2 + 30^2, so

   N = (33*17 + 30*10)*(33*17 - 30*10)/(33 + 30)*(33 - 30),
     = (561 + 300)*(561 - 300)/(63*3),
     = 861*261/(3^3*7),
     = (861/21)*(261/9),
     = 41*29.

This can be generalized to writing

   N = a^2 + k*b^2 = c^2 + k*d^2, 0 < a < c, 0 < d < b.

There are always values of k which can be used, no matter whether
N = 1 (mod 4) or N = 3 (mod 4).  Then N can be factored in the same
way as above.

For slightly larger numbers, I would try the Pollard Rho Method.  It
goes like this.  For factor N, start with x(0) as any convenient 
number except 0, 1, or -1, and for each n > 0, compute

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

Continue this until you find a d(n) with 1 < d(n) < N.  Then d(n) is a 
factor of N, which is then split into two smaller factors d(n) and 
N/d(n).  The worst-case time to factor a composite N is N^(1/4) steps.  
Small factors tend to be found before large ones, but not necessarily!

Again, if N = 1189, this proceeds as follows.  Let x(0) = 4.

   n   x(2*n-1)     x(2*n)     x(2*n) - x(2*n-1)     d(n)
   0                   4
   1      15         224             209               1
   2     237         285              61               1
   3     372         459             222               1
   4     227         401             116              29

Thus N = 29*41.

Another possibility is the Pollard P-1 method.  To factor N, start 
with x(1) = a, for some convenient integer a > 1, and for each n > 1, 
compute

   x(n) = x(n - 1)^n (mod N),
   d(n) = GCD[N, x(n) - 1].

Continue this until you find a d(n) with 1 < d(n) < N.  Then d(n) is a 
factor of N, which is then split into two smaller factors d(n) and 
N/d(n).  The worst-case time to factor a composite N is about sqrt(N) 
steps, but the average time for a random N is much smaller.  Small 
factors tend to be found before large ones, but not necessarily!

Again, let N = 1189.  Pick a = 2.  Then

   n  x(n)   d(n)
   1     2      1
   2     4      1
   3    64      1
   4   426      1
   5   575     41

So N = 41*29.

For really big numbers (scores of digits), the methods of choice are
two very complicated methods called the Elliptic Curve Method and the 
Number Field Sieve.  Explaining them is more than I can do in this 
message.

There are many other methods, too, which are effective in some
circumstances.  Some of their names are Fermat's Method, the Continued 
Fraction Method, and SQUFOF, among many others.

In any case, once you have split N into two factors, you should test 
the factors to see if either or both is composite.  If so, one should 
continue by trying to factor these smaller composite numbers using an 
appropriate method such as those above.  Compositeness testing is 
another whole problem!

Feel free to write again if I can help further.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/