Factoring Large Numbers
Date: 05/26/2000 at 12:07:20 From: Gabriel Lozano Subject: Factoring Large Numbers (Fermat) I am doing a report on Fermat and it says he developed a method for factoring large numbers. The theorem goes something like this: "If p is a prime number, a is an integer, and p is not a divisor of a, then p is a divisor of a(p-1) - 1." However I don't completely understand how this is used. I can see how you can take a number, then find another number that has the original number as a factor, but I do not understand how it is used to take a number and find its factors. Can you help me out? Thank you.
Date: 05/26/2000 at 20:42:57 From: Doctor Rob Subject: Re: Factoring Large Numbers (Fermat) Thanks for writing to Ask Dr. Math, Gabriel. There are two separate ideas here. One is the factoring method, so far unspecified. The other is the theorem that you quote, which is known as Fermat's Little Theorem. They are related in only an indirect way. Fermat's Little Theorem is used as a test of compositeness, as follows. You have a number p that you suspect may be prime, but don't know. You pick a number a which is relatively prime to p, that is, has no common factor with p. You compute the remainder when a^(p-1) - 1 is divided by p. If this is not 0, then the contrapositive of the theorem tells you that p is *not* prime after all, but is composite. If the remainder *is* 0, you aren't sure whether or not p is prime, but there is an excellent chance that it is. Now if you are faced with a number to factor, you may want to apply the above test. If it is composite, you will go ahead and try to factor it. If it is most likely prime, you wouldn't waste any work trying to factor it without first trying to prove that it is prime, which is much more likely. There certainly is no point trying to factor prime numbers. Fermat devised two factoring algorithms that I know about. The one with which his name is usually associated goes like this. Start with N, the composite number to be factored. Let a be the biggest integer with a^2 < N. Write down the following table: k a+k a-k GCD(a+k,N) GCD(a-k,N) 0 1 2 3 4 etc. and fill in the blanks in the table. If any of the GCD's are greater than 1, you have found a factor of N. For example, if one tries to factor 1037 by this method, you'll start with a = 32, k 32+k 32-k GCD(32+k,1037) GCD(32-k,1037) 0 32 32 1 1 1 33 31 1 1 2 34 30 17 so 1037 = 17*61. The other method is called the Difference of Squares Method. The general idea is to write N = a^2 - b^2 = (a+b)*(a-b). If you can find a and b which makes this true (aside from b = (N-1)/2, a = (N+1)/2, which aren't helpful), then you have factored N. Fermat did this by rewriting the equation in the form a^2 - N = b^2. Then he started with the smallest positive a with a^2 >= N. If a^2 - N is a perfect square, then that a and b = sqrt(a^2-N) will work. If it is not a perfect square, then up a by 1 and try again. The work is made easier if, instead of squaring (a+1) and then subtracting N from that, you simply add 2*a + 1 to the previous value, because (a+1)^2-N = (a^2-N)+2*a+1. For example, if one tries to factor N = 1037 by this method, you'll start with a = 33, and the work will look like this: a a^2 - N 2*a + 1 33 52 67 52 + 67 = 119 34 119 69 119 + 69 = 188 35 188 71 etc. 36 259 73 37 332 75 38 407 77 39 484 = 22^2 so 1037 = 39^2 - 22^2 = 61*17. You see that neither of these methods is related to Fermat's Little Theorem. - 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.