1. NCCU Academic Hub
  2. 學術產出
  3. College of Informatics
  4. Periodical Articles
  5. Item

學術產出-Periodical Articles

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

題名 On the improvement of Fermat factorization using a continued fraction technique
作者 Wu, M.-E.;Tso, R.;Sun, Hung-Min
貢獻者 資科系
關鍵詞 Composite numbers; Computational capability; Continued fraction; IFP; Integer factorization problem; Integer-N; Prime factors; Hardware; Software engineering; Algorithms
日期 2014-01
上傳時間 3-Jun-2015 12:33:11 (UTC+8)
摘要 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. © 2013 Published by Elsevier B.V. All rights reserved.
關聯 Future Generation Computer Systems, 30, 162-168
資料類型 article
DOI http://dx.doi.org/10.1016/j.future.2013.06.008
dc.contributor 資科系
dc.creator (作者) Wu, M.-E.;Tso, R.;Sun, Hung-Min
dc.date (日期) 2014-01
dc.date.accessioned 3-Jun-2015 12:33:11 (UTC+8)-
dc.date.available 3-Jun-2015 12:33:11 (UTC+8)-
dc.date.issued (上傳時間) 3-Jun-2015 12:33:11 (UTC+8)-
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/75549-
dc.description.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. © 2013 Published by Elsevier B.V. All rights reserved.
dc.format.extent 535193 bytes-
dc.format.mimetype application/pdf-
dc.relation (關聯) Future Generation Computer Systems, 30, 162-168
dc.subject (關鍵詞) Composite numbers; Computational capability; Continued fraction; IFP; Integer factorization problem; Integer-N; Prime factors; Hardware; Software engineering; Algorithms
dc.title (題名) On the improvement of Fermat factorization using a continued fraction technique
dc.type (資料類型) articleen
dc.identifier.doi (DOI) 10.1016/j.future.2013.06.008
dc.doi.uri (DOI) http://dx.doi.org/10.1016/j.future.2013.06.008