(3.236.6.6) 您好!臺灣時間:2021/04/22 19:09
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:侯雅芳
研究生(外文):Ya-Fang Hou
論文名稱:多個多項式二次篩法的改良
論文名稱(外文):An Improvement of The Multiple Polynomial Quadratic Sieve
指導教授:官大智官大智引用關係
指導教授(外文):Da-Jr Guan
學位類別:碩士
校院名稱:國立中山大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:43
中文關鍵詞:多個多項式二次篩法二次篩法因數分解
外文關鍵詞:the multiple polynomial quadratic sievefactoringquadratic sieve
相關次數:
  • 被引用被引用:2
  • 點閱點閱:343
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:18
  • 收藏至我的研究室書目清單書目收藏:0
大整數因數分解一直是困難的計算問題,也造就許多公開密碼系統的設計。官大智教授撰寫「GQS 大整數因數分解」為實作「多個多項式二次篩法 (The Multiple Polynomial Quadratic Sieve)」演算法(簡稱為 MPQS),並且在 2004 年成功的分解 RSA-130 的整數。在 MPQS 演算法的篩選 (sieve) 過程中,保留因數分解後還剩一個或兩個大質數的平滑數 (smooth number)分解式,可縮短篩選的時間,但會使最後分解基底 (factor base) 擴增的很大。本論文利用所保留下來的大質數,能盡量與平滑數分解式配對,可以有效地減緩分解基底擴增的情況,進而增快分解大整數的速度。本篇論文中,我們在一台 AIX Server 上實作此想法,並藉由觀察參數調整結果,做為改進「MPQS」效能的建議。
Large integer factoring problem is a difficult computing problem. The security of many public-key cryptograohy system depend on the large interger factoring problem. Dr. Guan implement 「The Multiple Polynomail Quadratic Sieve Algorithm」 and name the program 「GQS」. The program successfully factor RSA-130 interger in 2004. It can reduce the time of sieving that the MPQS algorithm retain the smooth number with one or two prime. But finally the size of factor basis is large. We use some of the prime retained by the MPQS algorithm to match with the smooth number and reduce the size of factor basis. And then we can reduce the time of factoring. In this paper, we implement our idea in a AIX server and the result of this paper can be a suggestion of the improvement of MPQS.
1 緒論.....................................................................................................................................................................................................................................1
1.1 前言..................................................................................................................................................................................................................................1
1.2 論文架構..........................................................................................................................................................................................................................2
2 Quadratic Sieve 演算法及相關數論介紹...........................................................................................................................................................................4
2.1 基礎數論介紹..................................................................................................................................................................................................................4
2.1.1 二次剩餘 (Quadratic Residue).......................................................................................................................................................................................4
2.1.2 雷建德符號 (Legendre symbol)....................................................................................................................................................................................4
2.1.3 加寇比符號 (Jacobi symbol).........................................................................................................................................................................................5
2.1.4 平滑數 (smooth number)...............................................................................................................................................................................................5
2.2 Kraitchik''s Scheme............................................................................................................................................................................................................5
2.3 二次篩法 (Quadratic Sieve)..............................................................................................................................................................................................6
2.4 多個多項式二次篩法 (The Multiple Polynomial Quadratic Sieve)..................................................................................................................................10
2.5 自初始型多個多項式二次篩法 (The Self Initializing Variant of the Multiple Polynomial Quadratic Sieve)...................................................................13
2.6 大質數和二個大質數型多個多項式二次篩法 (The Large Prime and Double Large Prime Variation of the Multiple Polynomial Quadratic Sieve).....15
3 程式介紹.............................................................................................................................................................................................................................17
3.1 程式構想..........................................................................................................................................................................................................................17
3.2 程式架構..........................................................................................................................................................................................................................18
3.3 演算法..............................................................................................................................................................................................................................19
3.3.1 gqsinit 子程式...............................................................................................................................................................................................................19
3.3.2 gqssieve 子程式............................................................................................................................................................................................................20
3.3.3 gqsmerge 子程式..........................................................................................................................................................................................................21
3.3.4 gqscombine 子程式......................................................................................................................................................................................................21
3.3.5 gqsieve 子程式.............................................................................................................................................................................................................22
3.3.6 gqscycle 子程式............................................................................................................................................................................................................23
3.3.7 gqsreduce 子程式.........................................................................................................................................................................................................23
3.3.8 gqsfactor 子程式...........................................................................................................................................................................................................24
4 實驗步驟與結果................................................................................................................................................................................................................25
4.1 實作環境.........................................................................................................................................................................................................................25
4.2 實驗步驟.........................................................................................................................................................................................................................25
4.3 實驗結果.........................................................................................................................................................................................................................28
4.4 結果分析與說明.............................................................................................................................................................................................................31
5 結論與未來展望................................................................................................................................................................................................................32
參考文獻...............................................................................................................................................................................................................................33
[1] W.R. Alford and C. Pomerance. Implementing the self initializing quadratic sieve on a distributed network. Manuscript, 1993.
[2] Johannes Buchmann and Volker Muller. Algorithm for factoring integers. available at http://www.cdc.informatik.tu-darmstadt.de/ buch-mann/Lecture%20Notes/Algorithms%20for%20factoring%20integers.pdf, 2005.
[3] D.J. Guan. Experience in factoring large integers using quadratic sieve. available at http://guan.cse.nsysu.edu.tw/note/gqs.pdf, 2003.
[4] H.Boender and H.J.J. te Riele. Factoring integers with large primes variations of the quadratic sieve. Report HM-R9513, Centrum voor Wiskunde en Informatica, 1995.
[5] D.E. Knuth. The Art of Computer Programming, volume 2. Addison-Wesley, Reading, Mass, 1981.
[6] M. Kraitchik. Th eorie des nombres. Tome II, Gauthier-Villars, Paris, 1926.
[7] Brandt Kurowski. The multiple polynomial quadratic sieve. available at http://brandt.kurowski.net/projects/mpqs/paper/mpqs.ps.gz, 1998.
[8] A.K. Lenstra and M.S. Manasse. Factoring with two large primes. Math-matics of Computation, (63(208)), 1994.
[9] P. Montgomery. private communication.
[10] C. Pomerance. Analysis and comparison of some integer factoring algorithm, in computational methods in number theory. Math. Centrum Tract, 154:89{139, 1982.
[11] Robert D. Silverman. The multiple polynomial quadratic sieve. Math. Comp., 48(117):329{339, 1987.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔