Math and Statistics Homework Help | Free Math and Statistics Homework Help |

Fermat's Factorization Technique

(In this tutorial, the word "number" means "positive integer")

There has been a surge of interest in prime factorization recently since it is the only known way to crack the RSA cryptosystem code. Currently, most of the best modern factoring algorithms are based on the idea behind Fermat's method of factorization. This tutorial will explain how to use Fermat's method to find the prime factorization of a number.

A **prime number** is a number greater than 1 that is
only divisible by 1 and itself. The first few primes are 2, 3, 5, 7, 11,
13, ...

**Factors** are numbers that are multiplied together to
get another number. For example, 3 and 4 are factors of 12 since 3*4 = 12.

**Factorization** or **factoring** of a number is
the decomposition of that number into a product of other numbers, which when
multiplied together give the original number.

When a number is written as a product of prime factors,
this is called the **
prime factorization** of that number. For example, 3*2*2 or 3*2^{2}
is the prime factorization of 12.

The **Fundamental Theorem of Arithmetic** says that
each number has a unique prime factorization. Below are a couple of
methods for finding it.

**Brute Force Method**

The Brute Force method calls for testing each of the primes up to the square
root of *n (the number to be factored)* for
divisibility. This method will certainly produce a factor if n is not
prime. The problem is that this technique is slow and for large *
numbers**
*which have no small prime factors (such as those used for the RSA
cryptosystem), the Brute Force method can not find a factor in a reasonable
amount of time.

**Fermat's Method**

Fermat knew that every odd number could be written as the difference of two
squares (n = a^{2} - b^{2}). The proof of this theorem is
below.

*Proof*:
Let n be an odd number and re-write n as n = m_{1}m_{2} with m_{1 }__
<__ m_{2} (m_{1} can equal 1). Since n is odd, m_{1}
and m_{2} are both odd. Let a = ½(m_{1} + m_{2}) and b =
½(m_{2} - m_{1}). Notice that a and b are both integers. Then m_{1}
= a-b and m_{2} = a+b, so n = m_{1}m_{2} = (a-b)(a+b) =
a^{2} - b^{2}.

Fermat used this theorem to devise a technique for finding
factors of large numbers significantly faster than the Brute Force method.
To factor a number by Fermat's method, squares **(**b^{2}**)** are
added to the number to be factored until the resulting sum is itself a square (n
+ b^{2} = a^{2}). The existence of b such that n + b^{2}
= a^{2} is guaranteed by the above theorem which says n = a^{2}
- b^{2}. When such a value of b is found, then factors of n can be
identified since n = a^{2} - b^{2} = (a+b)(a-b).

**For example, try to**
find a factor of n = 152,398,989. We must first evaluate the terms of the
sequence 152398989, 152398989 + 1^{2}, 152398989 + 2^{2},
152398989 + 3^{2}, ... to look for squares. We find one at
152398989 + 6^{2} = 152399025 = (12345)^{2}. Thus, n =
(12345)^{2} - 6^{2} = (12345+6)(12345-6) = (12351)(12339).
These two factors can then be factored by the same method.

Although the Factors Calculator is useful for solving schoolwork problems, it uses a method similar to the Brute Force method and even if your computer is very powerful, it will take a long time for it to factor 152,398,989 that way (I tried it and the calculator used up so much of my computer's CPU that I had to shut down my browser using Task Manager). However, this Large Number Factoring Calculator will find the factors of 152,398,989 in a fraction of a second using the idea behind Fermat's method.

Copyright © 2008 All rights reserved.