Improving fermat factorization algorithm by dividing modulus into three forms

Abstract

Integer Factorization (IF) becomes an important issue since RSA which is the public key cryptosystem was occurred, because IF is one of the techniques for breaking RSA. Fermat’s Factorization Algorithm (FFA) is one of integer factorization algorithms that can factor all values of modulus. In general, FFA can factor the modulus very fast in case that both of prime factors are very close. Although many factorization algorithms improved from FFA were proposed, it is still time – consuming to find the prime factors. The aim of this paper is to present a new improvement of FFA in order to reduce the computation time to factor the modulus by removing some iterations of the computation. In fact, the key of the proposed algorithm is the combination within the three techniques to check the forms of the modulus before making decision to leave some integers out from the computation. In addition, the proposed algorithm is called Multi Forms of Modulus for Fermat Factorization Algorithm (Mn-FFA). The experimental results show that Mn-FFA can reduce the iterations of computation for all values of the modulus when it is compared with FFA and the other improved algorithms.