An Integer Factorization Method Equivalent to Fermat Factorization

Abstract

Integer factorization problem had a great impact on security of many public key cryptosystems. Advancement in factoring increases the need to develop innovative public key cryptosystems. In this paper, a special purpose factorization method to find the factors of a composite number, which is the product of two distinct primes, is proposed. Fermat's method is theoretically important and many modern factorization algorithms like the quadratic sieve, multiple polynomial quadratic sieve, and number field sieves are based upon this method. The proposed scheme is equivalent to Fermat's method, and hence it can be used in such popular modern factorization methods. The steps involved in the algorithm are proved theoretically. Algorithm is illustrated numerically using Mathematica.