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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.