Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search