基於快速傅立葉轉換之低複雜度大整數乘法運算

Abstract

由於透過雲端運算(Cloud Computing)在網路上存取或運算資料愈趨普遍，安全性的問題也伴隨著產生。全同態加密(Fully Homomorphic Encryption)演算法可讓雲端伺服器直接對密文進行運算，以維持資料的隱私性。然而，此演算法目前仍需龐大的計算來確保安全性，其運算元長度可達百萬位元以上，造成整體系統運算效率受到限制。區塊式(Block-based)快速傅立葉轉換(Fast Fourier Transform)乘法演算法可實現大整數乘法運算，但隨著所劃分的區塊數目增加，乘法和加法的運算次數會相應增加，導致整體運算複雜度也會跟著提升，如何開發出有效率的大整數乘法演算法是一個重要課題。 本論文所提出的區塊式快速傅立葉轉換乘法演算法，主要是針對奇偶區塊的輸入資料設計不同的排列方式，並藉由奇偶區塊的快速傅立葉轉換結果的結合，取得結合區塊的快速傅立葉轉換結果，將這三類區塊的快速傅立葉反轉換結果經由累加和進位計算可得到大整數乘法結果。此外，透過改變區塊間的執行順序，可進一步降低累加計算所需的儲存空間。相較於現有之區塊式快速傅立葉轉換乘法演算法，本論文所提出之方法可減少快速傅立葉轉換、點對點乘法以及快速傅立葉反轉換的運算次數，及降低總運算複雜度。

Date of Award	2016 Aug 25
Original language	Chinese
Supervisor	Ming-Der Shieh (Supervisor)