向量加法鍊之特性研究

Abstract

向量加法鍊是一個由向量組成的數列，數列中每個向量都是其前任兩個向 量的和。向量加法鍊可以解決以最少的乘法次數計算指數連乘積的問題。 在此，指數的次方為正整數，而指數的底數可以是任一個其乘法運算符合 結合律的集合。向量加法鍊的研究在數論、電腦科學、密碼系統等領域有 極重要的價值。舉例來說，現代公開金匙密碼系統的安全性是基於需使用 模指數連乘積的數學方法；然而，大量模指數連乘積的運算同時也令系統 的運作相當緩慢。許多學者曾經探討計算單一指數的加法鍊性質及計算方 法。儘管如此，加法鍊的性質至今仍未被徹底認識，而向量加法鍊的研究 也只在起步階段。另一方面，為了因應電腦系統速度上的需求，更快速的 指數連乘積計算方法也極待研發。因此，這兩方面的研究很值得繼續深入 。本論文旨在探討向量加法鍊的性質，我們針對電腦處理指數連乘積計算 時相關的向量加法鍊特性，進行理論證明及運算方法上的研究。論文第三 章提出並證明在某些情況下最短向量加法鍊之下限。此外，當各指數的二 進位表示具有相同型態時的最短向量加法鍊之長度，及求得此最短向量加 法鍊的方法也被提出。為了因應密碼系統速度上的需求，本論文亦考慮以 多處理機平行運算來加快模指數連乘積的計算。我們在第四章提出的平行 多維二元法，以及平行合併二元法快於所有已知的平行或非平行的計算方 法。文中也提出平行向量加法鍊的觀念，並且證明所提出的平行合併二元 法相當接近最短平行向量加法鍊的下限。此外，文第五章提出加法鍊的比 重長度觀念。當電腦系統中平方運算比乘運算快速時，此新觀念能更合理 地評量加法鍊長度與指數計算時間的關係。論文中提出最短比重長度加法 鍊的上限，並探討比重長度加法鍊與傳統加法鍊的異同。向量加法鍊的研 究具有學理探討及實際應用的價值，尤其從現代電腦密碼系統的需求來看 ，向量加法鍊的研究在今日更具實用性。本論文的研究成果，在增進對向 量加法鍊特性的瞭解，以及設計更快速的指數連乘積計算方法上具有貢獻 。最後，第六章列舉了一些關於向量加法鍊的研究方向、方法及待解問題 ，可提供未來的研究參考。 The vectorial addition chain is an optimal approach for computing a multi-exponentiation with the minimum number of multiplications. Here ni is a positive integer and xi is an element of a set in which an associative multiplication is defined. The properties of vectorial addition chains can be applied to the number theory, computer science, and cryptology. This dissertation merits the exploration of some properties of vectorial addition chains and the proposing of some methods that can increase the performance of multi-exponentiation evaluations. The length of the shortest vectorial addition chain as well an approach to achieve the shortest chains in some cases are presented. In order to fulfill the speed requirement in modern cryptosystems, we used the parallel processing technique to increase the speed of the modular multi- exponentiation computation. The concept of the shortest prallel vectorial addition chains, which is an optimal approach for computing the modular multi- exponentiation in parallel, is also given. In addition, the concept of the shortest weighted length addition chains is presented. This concept provided a more reasonable approach to characterize the performance of an addition chain when the computation time of a squaring is no less than that of a multiplication.