1. NCCU Academic Hub
  2. 學術產出
  3. 資訊學院
  4. 會議論文
  5. Item

學術產出-會議論文

文章檢視/開啟

書目匯出

Google ScholarTM

政大圖書館

引文資訊

TAIR相關學術產出

題名 On the improvement of fermat factorization
作者 Wu, M.-E.;Tso, R.;Sun, H.-M.
左瑞麟
貢獻者 資科系
關鍵詞 Composite numbers; Continued fraction; Cryptanalysis; Integer factorization; Integer-N; Prime factors; SIMPLE method; Algorithms; Factorization; Network security
日期 2012
上傳時間 17-四月-2015 11:39:43 (UTC+8)
摘要 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, 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. © 2012 Springer-Verlag.
關聯 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volume 7645 LNCS, 380-391
資料類型 conference
DOI http://dx.doi.org/10.1007/978-3-642-34601-9_29
dc.contributor 資科系
dc.creator (作者) Wu, M.-E.;Tso, R.;Sun, H.-M.
dc.creator (作者) 左瑞麟zh_TW
dc.date (日期) 2012
dc.date.accessioned 17-四月-2015 11:39:43 (UTC+8)-
dc.date.available 17-四月-2015 11:39:43 (UTC+8)-
dc.date.issued (上傳時間) 17-四月-2015 11:39:43 (UTC+8)-
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/74658-
dc.description.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, 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. © 2012 Springer-Verlag.
dc.format.extent 176 bytes-
dc.format.mimetype text/html-
dc.relation (關聯) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volume 7645 LNCS, 380-391
dc.subject (關鍵詞) Composite numbers; Continued fraction; Cryptanalysis; Integer factorization; Integer-N; Prime factors; SIMPLE method; Algorithms; Factorization; Network security
dc.title (題名) On the improvement of fermat factorization
dc.type (資料類型) conferenceen
dc.identifier.doi (DOI) 10.1007/978-3-642-34601-9_29
dc.doi.uri (DOI) http://dx.doi.org/10.1007/978-3-642-34601-9_29