Efficient multiplication for long integers

淡江大學機構典藏 > 工學院 > 資訊工程學系暨研究所 > 學位論文 > Item 987654321/35130

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/35130

题名:	Efficient multiplication for long integers
其它题名:	有效的長整數乘法
作者:	黃龍信;Huang, Loang-shing
贡献者:	淡江大學資訊工程學系碩士在職專班黃仁俊;Hwang, Ren-junn
关键词:	典型乘法;RSA演算法;Classical Multiplication;Karatsuba-Ofman Method;DH Scheme;Divide-and-Conquer Method;RSA Algorithm
日期:	2006
上传时间:	2010-01-11 06:03:16 (UTC+8)
摘要:	本篇論文呈現一種分割的方法，用來加速乘法的運算速度。此種方法是基植於所謂分割然後擊破的觀念並且相當適合於現今微處理器的運算架構。首先，我們呈現的是如何去找到可以分割的最小長度，只要比這個長度還大的運算元，使用分割的方法會比只單純使用典型乘法的效能還要好；另一方面，比這個最小長度還小的運算元，當我們在實現多精確乘法時，只能使用典型乘法來實現，因為此時典型乘法會比分割的方法要有較佳的效能。這個最小的長度為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.
显示于类别:	[資訊工程學系暨研究所] 學位論文

文件中的档案:

档案	大小	格式	浏览次数
	0Kb	Unknown	323	检视/开启

在機構典藏中所有的数据项都受到原著作权保护.

TAIR相关文章

数据加载中.....