摘要
本篇論文呈現一種分割的方法，用來加速乘法的運算速度。此種方法是基植於所謂分割然後擊破的觀念並且相當適合於現今微處理器的運算架構。首先，我們呈現的是如何去找到可以分割的最小長度，只要比這個長度還大的運算元，使用分割的方法會比只單純使用典型乘法的效能還要好；另一方面，比這個最小長度還小的運算元，當我們在實現多精確乘法時，只能使用典型乘法來實現，因為此時典型乘法會比分割的方法要有較佳的效能。這個最小的長度為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.
參考文獻
延伸閱讀
- 謝金石、Kin-Shue Hsieh（1989）。序向二進位正整數乘法器之設計。資訊縮影管理，(12)，34-47。https://www.airitilibrary.com/Article/Detail?DocID=a0000488-198903-x-12-34-47-a
- 張恩惠（2020）。一個可應用於數位訊號處理之簡單而精確的定寬乘法器設計〔碩士論文，中原大學〕。華藝線上圖書館。https://doi.org/10.6840/cycu202000630
- 林美伶（釋堅融）（2010）。《教乘法數》文獻與定位考〔碩士論文，淡江大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0002-2701201023581900
- 劉偉羿（2015）。高精確度及面積效益的固定長度布爾乘法器〔碩士論文，中原大學〕。華藝線上圖書館。https://doi.org/10.6840/cycu201500079
- 林哲緯（2013）。The Implementation of Efficient Large Integer Modular Reduction Method〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2013.01015