淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2606200620370500
中文論文名稱 有效的長整數乘法
英文論文名稱 Efficient Multiplication for Long Integers
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士在職專班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 94
學期 2
出版年 95
研究生中文姓名 黃龍信
研究生英文姓名 Loang-Shing Huang
學號 793190231
學位類別 碩士
語文別 英文
第二語文別 英文
口試日期 2006-06-14
論文頁數 53頁
口試委員 指導教授-黃仁俊
委員-黃心嘉
委員-何煒華
中文關鍵字 典型乘法  RSA演算法 
英文關鍵字 Classical Multiplication  Karatsuba-Ofman Method  DH Scheme  Divide-and-Conquer Method  RSA Algorithm 
學科別分類 學科別應用科學資訊工程
中文摘要 本篇論文呈現一種分割的方法,用來加速乘法的運算速度。此種方法是基植於所謂分割然後擊破的觀念並且相當適合於現今微處理器的運算架構。首先,我們呈現的是如何去找到可以分割的最小長度,只要比這個長度還大的運算元,使用分割的方法會比只單純使用典型乘法的效能還要好;另一方面,比這個最小長度還小的運算元,當我們在實現多精確乘法時,只能使用典型乘法來實現,因為此時典型乘法會比分割的方法要有較佳的效能。這個最小的長度為14字元,並且我們稱它為臨界長度。其次,假若運算元的長度很長時,我們發現將運算元一直重覆切割成相等的兩部份,直到發現切割的長度比臨界長度小時就停止切割,此時再使用典型乘法實現該部份的多精確乘法,而後往前完成整個多精確乘法。該種分割方法不僅可以改善乘法的效能,且具有實現容易的優點,有助於實現對於模乘法與模指數運算此種須要大量乘法運算的架構,因而對於提升現今傳統公開金鑰密碼系統的效能有重要的幫助。
英文摘要 This thesis presents a split method to accelerate the performance of multiprecision multiplication, which is based on the concept of divide-and-conquer and can be operated on word boundary in order to fit with the architecture of modern microprocessors. First, we demonstrate the minimal operand’s length which can be split such that using the split way has better performance than the classical multiplication (no split). This length is 14 and we call it the threshold length. Second, if the operand’s length is greater than or equal to the threshold length, the split way we proposed will have the better performance among all different kinds of split ways and we call it recursive (balanced) 2-way split. This method not only accelerates the performance of the multiprecision multiplication, but also reduces the computational timing of modular multiplication and modular exponentiation. Therefore it can be used to speeds up the public-key cryptographic system on microprocessors such as RSA or Diffie-Hellman key exchange.
論文目次 Chapter 1 Introduction...………………………………………………1
Chapter 2 Related Works……………………………………………..3
2.1 Classical Multiplication………………………………………...3
2.2 Karatsub-Ofman Method……………………………………...6
Chapter 3 Our Proposal Method……………………………………12
Chapter 4 Analysis of the Proposal Method………………………..15
4.1 Two Basic Split Ways………………………………………….15
4.1.1 Depth-1 Balanced Splits for s-word Integers………….15
4.1.2 Depth-n Balanced Splits for s-word Integers…………22
4.2 The Minimal Cost for These Two Basic Split Ways…………30
4.3 The Threshold Length, ST…………………………………….34
Chapter 5 Experiments………..………………………………………36
5.1 Architecture of TI DSP C55x family…………………………36
5.2 RSA Cryptosystem and Its Components…………………….38
5.3 Experiment Results……………………………………..……..41
Chapter 6 Conclusions and Future Works………………………...…48
References………………………………………………………………49
The Optimal Method for Long Integer Multiplication on
Microprocessors………………………………………………………..50

Figure 1 Graphical representation of the classical multiplication…...4
Figure 2 Graphical representation of the Karatbu-Ofman Method....7
Figure 3 t-way split at depth 1…………………………………….......15
Figure 4 Graphical representation of Equation (3)……………...…..17
Figure 5 4-way split at depth 1…………...…………………………...21
Figure 6 2-way split at depth n…………...…………………………...23
Figure 7 2-way split at depth 3…………...…………………………...28
Figure 8 Graphical representation of TMS320C55x………..……….38
Figure 9 Graphical representation of Table 16……………..………..43
Figure 10 Graphical representation of Table 17………….……….…44
Figure 11 Graphical representation of Table 18……………………..45

Table 1 Base instructions for the classical multiplication…………….5
Table 2 Some data for the classical multiplication……………………6
Table 3 Base instructions for a multiprecision addition/subtraction...9
Table 4 Number of classical multiplication, multiprecision addition/subtraction for 2-way split at depth 1……………..10
Table 5 Base instructions for 2-way split at depth 1…………………10
Table 6 Some data for 2-way split at depth 1………………………...10
Table 7 Number of classical multiplication, multiprecision
addition/subtraction for Equation (4) or (5)………………..19
Table 8 Base instructions for Equation (4) or (5)…………………….19
Table 9 Base instructions for Equation (6)…………………………...22
Table 10 Base instructions for Equation (9)…………………..……...28
Table 11 Base instructions for Equation (10)…………………..…….29
Table 12 Total number of base instructions for Theorems 1 and 2…30
Table 13 Some data for t, s and total base instructions……………...31
Table 14 Some data of t, s and total base instructions for
cryptographic application…………………………………..32
Table 15 Some useful data for n, s and total base instructions for
cryptographic application…………………………………..33
Table 16 Experiments for the multiplication…………………………42
Table 17 Experiments for modular multiplication…………………..43
Table 18 Experiments for modular exponentiation………………….44
Table 19 Split ratio for unbalanced split way………………………..45
Table 20 Experiments for the multiplication with unbalanced split
way…………………………………………………………...46


參考文獻 [1] A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997.
[2] W. Diffie and M.E. Hellman, “New directions in cryptography,” IEEE Trans. On Information Theory, vol.IT-22, no.6, pp.638-654, Nov. 1976.
[3] A.Karatsuba and Y. Ofman, “Multiplication of multidigit numbers on automata,” Soviet Phys. Doklagy, vol.7, no.7, pp595-596, 1963.
[4] R. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communication on ACM, vol.21, pp.120-126, 1978.
[5] D.E. Knuth, The Art of Computer Programming, Vol 2, Addison-Wesley, 1969, 3rd edition, 1998.
[6] D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2004.
[7] Texas Instruments, “C5000 DSPs : Architecture & Peripheral Features,” Available: http://www.ti.com, 2006/6/2.
[8]MapleSoft, Available: http://www.maplesoft.com, 2006/6/2
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2008-07-13公開。
  • 同意授權瀏覽/列印電子全文服務,於2008-07-13起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信