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