Fermat's Method of Factoring

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² 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² - b²). The proof of this theorem is below.

Proof: Let n be an odd number and re-write n as n = m₁m₂ with m₁ < m₂ (m₁ can equal 1). Since n is odd, m₁ and m₂ are both odd. Let a = ½(m₁ + m₂) and b = ½(m₂ - m₁). Notice that a and b are both integers. Then m₁ = a-b and m₂ = a+b, so n = m₁m₂ = (a-b)(a+b) = a² - b².

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²) are added to the number to be factored until the resulting sum is itself a square (n + b² = a²). The existence of b such that n + b² = a² is guaranteed by the above theorem which says n = a² - b². When such a value of b is found, then factors of n can be identified since n = a² - b² = (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², 152398989 + 2², 152398989 + 3², ... to look for squares. We find one at 152398989 + 6² = 152399025 = (12345)². Thus, n = (12345)² - 6² = (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.