Fermat's Factorization Method
Fermat’s factorization method is an algorithm for breaking down an integer \( n \) into two factors by expressing \( n \) as the difference of two squares:\[ n = x^2 - y^2 = (x + y)(x - y) \]
How does it work?
The method follows these steps:
- Start with an odd integer \( n \): If \( n \) is even, keep dividing by 2 until you get an odd number.
- Find the smallest integer \( k \) such that \[ k^2 \geq n \] In other words, compute \( k = \lceil \sqrt{n} \rceil \), the smallest integer greater than or equal to the square root of \( n \).
- Search for an integer \( x \) such that \( x^2 - n = y^2 \) is a perfect square, beginning with \( x = k \).
- If \( x^2 - n \) is not a perfect square, increment \( x \) and check again.
- Once a perfect square is found, we can express \( n \) as: \[ n = (x+y) \cdot (x-y) \] The numbers \( x+y \) and \( x-y \) provide a factorization of \( n \).
This factorization is not necessarily in prime numbers.
If the factors are not prime, apply the same process to each of them.
Note: Fermat’s method is particularly effective when the factors of \( n \) are close in value—i.e., when \( n \) is the product of two large, similar numbers. However, if the factors are highly unbalanced (one large, one small), the method becomes inefficient because it may take many iterations to find a perfect square.
A Practical Example
Let’s factorize \( n = 5959 \).
First, compute \( k \):
\[ \sqrt{5959} \approx 77.2 \Rightarrow k = 78 \]
Now, compute \( k^2 - n \):
\[ 78^2 - 5959 = 6084 - 5959 = 125 \]
Since 125 is not a perfect square (\( \sqrt{125} \approx 11.18 \)), increment \( k \) and try again.
\[ 79^2 - 5959 = 6241 - 5959 = 282 \]
282 is still not a perfect square (\( \sqrt{282} \approx 16.79 \)), so we keep going.
What is a perfect square? A perfect square is an integer that can be written as the square of another integer: $$ y = x^2 $$ For example, \( y = 25 \) is a perfect square because \( y = 5^2 \). To check if a number is a perfect square, compute its square root: if \( \sqrt{y} \) is an integer, then \( y \) is a perfect square. For instance, \( \sqrt{25} = 5 \).
Continuing the search:
\[ 80^2 - 5959 = 6400 - 5959 = 441 \]
\[ 81^2 - 5959 = 6561 - 5959 = 602 \]
\[ 82^2 - 5959 = 6724 - 5959 = 765 \]
\[ 83^2 - 5959 = 6889 - 5959 = 930 \]
\[ 84^2 - 5959 = 7056 - 5959 = 1097 \]
\[ 85^2 - 5959 = 7225 - 5959 = 1266 \]
\[ 86^2 - 5959 = 7396 - 5959 = 1437 \]
\[ 87^2 - 5959 = 7569 - 5959 = 1610 \]
\[ 88^2 - 5959 = 7744 - 5959 = 1785 \]
\[ 89^2 - 5959 = 7921 - 5959 = 1962 \]
\[ 90^2 - 5959 = 8100 - 5959 = 2141 \]
Finally, we find a perfect square:
\[ 91^2 - 5959 = 8281 - 5959 = 2322 = 48^2 \]
Thus, we can rewrite \( n \) as a difference of squares:
\[ n = x^2 - y^2 = (x + y)(x - y) \]
Here, \( x = 91 \) and \( y = 48 \), so:
\[ 5959 = (91 + 48) \cdot (91 - 48) = 139 \times 43 \]
Therefore, \( 5959 = 139 \times 43 \), giving us the factorization of \( n \).
Since both 139 and 43 are prime, the factorization is complete.
To confirm, we check whether these numbers have any prime divisors other than 1 and themselves.
The number 139 is prime because:
- It’s odd, so it’s not divisible by 2.
- The sum of its digits is \( 1 + 3 + 9 = 13 \), which is not divisible by 3.
- It doesn’t end in 0 or 5, so it’s not divisible by 5.
- Checking divisibility against primes up to \( \sqrt{139} \approx 11.79 \), none of 2, 3, 5, 7, or 11 divide 139.
The number 43 is prime because:
- It’s odd, so it’s not divisible by 2.
- The sum of its digits is \( 4 + 3 = 7 \), which is not divisible by 3.
- It doesn’t end in 0 or 5, so it’s not divisible by 5.
- Checking divisibility against primes up to \( \sqrt{43} \approx 6.56 \), none of 2, 3, or 5 divide 43.
Example 2
Fermat’s factorization method is particularly effective when the number \( n \) has factors that are close to \( \sqrt{n} \).
For example, let's take the number:
$$ n = 127433 $$
First, we determine the initial value of \( k \):
\[ \sqrt{127433} \approx 356.97 \Rightarrow k = 357 \]
Next, we compute \( k^2 - n \):
\[ 357^2 - 127433 = 127449 - 127433 = 16 = 4^2 \]
Since \( 16 \) is a perfect square, we immediately obtain the factors of \( n \) in just one step.
\[ n = x^2 - y^2 = (x + y)(x - y) \]
In this case, we have \( x = 357 \) and \( y = 4 \), so:
\[ 127433 = (357 + 4) \cdot (357 - 4) = 361 \cdot 353 \]
And that’s the complete factorization!
Remarks
Some key insights into Fermat’s method:
- Fermat’s method has exponential complexity
While Fermat’s factorization method is elegant and easy to understand, it suffers from exponential complexity in the worst case. As a result, it is generally impractical for factoring large numbers and is largely superseded by more efficient algorithms such as the Quadratic Sieve and the Number Field Sieve.Note. Fermat’s method is most effective when the factors of \( n \) are relatively close in magnitude, meaning that \( n \) can be expressed as the product of two numbers \( a \) and \( b \) such that: \[ a \approx b \approx \sqrt{n} \] However, its efficiency rapidly deteriorates when one factor is significantly larger than the other, leading to an exponential number of steps.
And so on.
