本篇論文呈現一種分割的方法，用來加速乘法的運算速度。此種方法是基植於所謂分割然後擊破的觀念並且相當適合於現今微處理器的運算架構。首先，我們呈現的是如何去找到可以分割的最小長度，只要比這個長度還大的運算元，使用分割的方法會比只單純使用典型乘法的效能還要好；另一方面，比這個最小長度還小的運算元，當我們在實現多精確乘法時，只能使用典型乘法來實現，因為此時典型乘法會比分割的方法要有較佳的效能。這個最小的長度為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