Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6873663 | Future Generation Computer Systems | 2014 | 7 Pages |
Abstract
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, pE+qE and pEâ
qE, 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mu-En Wu, Raylin Tso, Hung-Min Sun,