Hasan and Hussain are two Arabian friends who live in Medina. Once they were discussing how to factorize a given number. Hasan told Hussain that there exists a super fast factorization method that can find two numbers whose product is equal to the given number. Hussain asked Hasan to explain that method to him. Hasan said that this method was devised by the great mathematician Fermat. Hasan said to Hussain that if he gives him a pack of dates, then he will explain the method to him. Hussain happily agrees to Hasan’s demand and gives him a pack of dates. Now Hasan starts explaining Fermat’s Factorization method to Hussain.
Let’s dive deep into mathematics and try to understand Fermat’s factorization method in a detailed manner. Given a positive integer N, we can find its factors only if it is an odd number. Keep in mind that this algorithm doesn’t work for even numbers.
Problem Statement:
Given a positive odd integer N, find two numbers that divide N completely.
Approach:
Fermat’s factorization method relies on the fact that every odd number can be represented as a difference of squares of two numbers. That is,
N = X ^ 2 - Y ^ 2 = (X + Y) * (X - Y). Here ‘X’ is greater than ‘Y’ and (x + y) and (x - y) are factors of N.
We start with finding an integer ‘K’ such that K * K is greater than N.
Then we find the difference between K * K and N. Let the difference be denoted as D.
If D is a perfect square, then we stop. Let S be the square root of D. Therefore, our answer is given by “S * S - K * K”. As a result, factors of N are given by (S - K) and (S + K).
Note: A perfect square is a number from a given number system such that it can be expressed as a square of a number from the same number system. For example, 64, 16, 100 are perfect squares, whereas 13, 17, 99 are not.
Steps:
Find a positive integer K such that K * K is greater than N, i.e., K * K >= N.
Let variable D = K * K - N.
If D is a perfect square, then we are done. Go to step 5.
Else increment K by 1. That is K = K + 1. Repeat step 2.
Find the square root of D. Let S * S = D. Then, the factors of ‘N’ are given by (S - K) and (S + K).
Now let us work upon an example to understand these steps clearly.
Let the given number N be 23247. According to Fermat’s factorization method, we find a number K such that K * K is greater than N.
Step 1: Generate a number K such that its square is greater than N. So, we find 153 * 153 >= 23247. So our pick for K is 153.
Step 2: The difference between 153 * 153 - 23247 is equal to 162.
Step 3: Is 162 a perfect square? The answer is no. So we go to step 4.
Step 4: K = K + 1. Therefore K = 154 now. Repeat step 2.
Step 2
Step 3
Step 4
154 * 154 - 23247 = 469
469 is not a perfect square.
K = K +1
K = 155
155 * 155 - 23247 = 778
778 is not a perfect square.
K= K+1
K=156
156 * 156 - 23247 = 1089
1089 is a perfect square
Stop
Now, N = K * K - D. That is N = (K * K) - (S * S). Therefore 23247 = (156 * 156) - (33 * 33). So 23247 = (156 - 33) * (156 + 33) = (128) * (189). Therefore the factors of our number N = 23247 are 128 and 189.
Now let us take another example. Let the value of N = 333. Using Fermat’s factorization method, find two positive integers, which are factors of the given number N. First, we find a number whose square is greater than 333. So K = 19.
Therefore K = 23 and D = 196. Now N = K * K - D.That is 333 = 23 * 23 -196 = 23 * 23 - 14 * 14. So 333 = (23 + 14) * (23 - 14). Therefore N = 333 = 37 * 9.
longlongint K = sqrt(N); longlongint D, S; K = K + 1;
while (true) { D = K * K - N; S = sqrt(D); if (S * S == D) { break; } K = K + 1; }
cout << "The factors of " << N << " are " << K - S << " and " << K + S << "." << endl; return; } intmain() { longlongint N; cout << "Enter a number whose factors are to be found: "; cin >> N; findFactors(N); return0; }
Input:
Enter a number whose factors are to be found: 95687
Output
The factors of 124567 are 103 and 929.
Time Complexity:
The time complexity of the above code is O(|P - Q|) where P and Q are factors of N.
Space complexity:
The space complexity of the above code is O(1), as no auxiliary space is required in this case.
Practice Problems
Would you mind visiting Coding Ninjas Studio and practice some famous interview problems on Fermat’s Factorization method. After coding up these problems, you will gain solid confidence in this method.
In this blog, we learned about an important algorithm, namely, Fermat’s Factorization method. We learned how to implement the method in C++ and saw some of its essential applications. Do practice the coding problems and add a feather to your knowledge in the Number system.
38+ registered 