An Improvement of Fermat's Factorization by Considering the Last m Digits of Modulus to Decrease Computation Time
Kritsanapong Somsuk, Kitt Tientanopajai · International journal of network security · 2017
Fermat's Factorization Algorithm (FFA) and the algorithms improved from FFA are the fast integer factorization algorithms when these algorithms are chosen to find two large prime factors of the balanced modulus. The key is a process to find two perfect squares such that their difference is equal to the modulus. However, it is time-consuming to find these two integers because there is only one solution but many integers are chosen in this experiment to find the solution. In this paper, a new improvement of FFA is proposed by leaving out some unrelated integers, which do not affect getting the correct solution. Leaving out these integers results from analyzing the last m digits of the modulus where m is a positive integer. The new faster and improved algorithm is called Specific Fermat's Factorization Algorithm Considered from X (SFFA-X) where X is represented as the last m digits of the modulus. The experimental results showed that SFFA-X can factor the modulus faster than FFA and many modified algorithms of FFA especially when at least 2 digits of X are chosen for the implementation.