On the improvement of Fermat factorization using a continued fraction technique

摘要

Although Integer Factorization Problem (IFP) is one of the most difficult problems in the world due to the limited computational capability, there exist some vulnerable integers which are factorable by the development of cloud computing. For example, given an integer N = pq, which is a product of two primes, it is hard to determine the prime factors p and q efficiently. However, for the suitable size of a number N, Fermat's algorithm may be one of the simplest method for solving it. In this paper, a method called EPF for estimating the prime factors of a composite number is proposed. We use the technique of continued fractions to output two integers, p_E + q_E and p_E · q_E, which are close to p + q and p · q, respectively. Furthermore, we show that EPF can be adopted to reduce the loop count in Fermat's algorithm before factoring a composite number. The effect depends on the size of the prime factor. We believe that there are still other applications as well wherein EPF can be used.