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/