Abstract
Given an integer N = pq, which is a product of two primes, it is difficult to determine the prime factors p and q efficiently. However, for the suitable size of a number N, Fermat's algorithm is one of the most simple 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. © 2012 Springer-Verlag.