請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10392
標題: | 使用較少記憶體的F4演算法 A time-memory tradeoff in Faugère's algorithm for computing Gröbner bases |
作者: | Yun-Ju Huang 黃筠茹 |
指導教授: | 陳君明(Jiun-Ming Chen) |
關鍵字: | 密碼學,代數密碼分析,解方程組,Groebner基底,Faugere的F4演算法,時間與空間的權衡, Cryptography,algebraic cryptanalysis,system solver,Groebner basis,Faugere’s F4 algorithm,time-memory trade-off, |
出版年 : | 2010 |
學位: | 碩士 |
摘要: | 解多變量多項式方程組,不論是對於破解多變量密碼系統的應用而言或者對 於多變量多項式方程組的研究本身,都是個重要的課題。 目前大部分有效解多 變量多項式系統的演算法,大多是利用多變數環中Gröbner-basis 的特性而轉為 求Gröbner-basis的演算法, 包括XL演算法以及Faugère的F4、F5演算法。
F4演算法是一個相當有效率的計算Gröbner-basis的演算法。即便如此,演算法 本身的時間跟空間複雜度依然隨變數個數n成指數成長。這使得我們在想要解較大的多變量方程組系統情況下,將不可避免的碰到了執行面上得瓶頸。 例如,假設現在有一個變數個數n = 40且方程式個數m = 40的系統,若想要利用F4來解此方程組,現有的絕大部分電腦都會遭遇硬體無法負荷的情形,以致在解出答案前就用光了所有的記憶體。縱然F4本身有機制可以對記憶體用量稍作調整,但是效益很低。 在本篇論文中,我們開始思考下列幾個關於F4的記憶體資源使用的問題: 1. 能不能讓F4演算法,或者其變型,在任何記憶體限制下都能夠執行? 2. 如果不能,F4演算法至少需要多少記憶體才能夠執行? 3. 若給予更多記憶體,能不能使修改過的F4 演算法執行的更快? 透過回答上述問題,我們觀察到F4的每個步驟的記憶體使用情況,而據此我們針對F4演算法提出一些建議以修改記憶體的使用問題。我們修改過後的F4演算法較原本的演算法使用更少的記憶體。更甚者,修改過後的演算法在相同記憶體之下執行速度比原本的F4演算法快。而透過將大量的運算拆成許多較小的運算子集再分別一一運算,我們的演算法成功對其記憶體消耗量作出控制。當然這實際上是在時間與空間上作權衡,而將時間去換取空間的結果。由於我們修改過後的F4演算法需要更多的控制檢查,而在記憶體有限的情況之下,很多資訊無法儲 存而必須重複計算。 透過計算用時間與空間積值,利用以下幾點我們可以說明新的F4演算法在時間與空間的權衡上是有意義的,且提供了相當的彈性。 1. 我們的修改演算法平均上較原本的 F4 演算法有更小的時間與空間的乘積。 2. 只要記憶體大於計算所需的最小記憶體需求,我們的修改過的F4 演算法可以在任意的記憶體限制環境下計算 Gröbner-basis。 3. 若我們的演算法使用越多的記憶體,則執行的越快。 在論文最後,我們實做了原F4演算法以及修改過後的演算法原型,並得到大量組別的實驗數據。 多組不同參數的實驗數據驗證我們修改過後的演算法的確達到上述的研究目標。例如:使用者只要多花兩倍的執行時間,就可以用10%的記憶體執行F4演算法。 Solving multivariate systems of polynomial equations is an important problem both as a subroutine in algebraic cryptanalysis and in its own right. Currently, the most efficient solvers are the Gröbner-basis solvers, which include the XL algorithm, as well as Faugère's F4 and F5 algorithms. The F4 algorithm is an advanced algorithm for computing Gröbner basis. However, the algorithm has exponential space complexity. This poses a serious challenge when we want to use it to solve instances of sizes of practical interest. For example, if we are going to solve a multivariate polynomial system of 40 equations in 40 variables, then most of today's computers will run out of memory before the execution of the algorithm finishes. Furthermore, the original F4 algorithm does not provide much flexibility in terms of controlling memory usage. In this thesis, we set out to address this shortcoming by starting with the following questions about F4's memory consumption. 1. Can F4 , or any variant of it, be executed under any memory limitation? 2. If not, at least how much memory is necessary for F4 to be successfully executed? 3. Can we make the modified F4 algorithm run faster when given more memory? Throughout the process of answering these questions, we observe the memory usage in each part of the F4 algorithm, based on which we propose modifications to the algorithm. Our modified F4 algorithm uses less memory than the original algorithm. More importantly, our modified F4 algorithm runs faster than the original algorithm using the same amount of memory. Our modified F4 algorithm controls its memory consumption by dividing the work into chucks of smaller working sets and executing them one at a time. This in effect trades time for memory because it involves more computation, some of which might even be carried out repeatedly. We will show that such a trade-off makes sense in terms of time-memory product and is extremely flexible by showing the following. 1. Our modification on average yields smaller time-memory products than the original F4 algorithm. 2. Our modified F4 algorithm allows the Gröbner basis be computed using an arbitrary amount of memory as long as it is above the minimum amount of memory required to solve the instance. 3. The more memory our modified F4 algorithm uses, the faster it runs. We have implemented a prototype of the proposed modified F4 algorithm and conducted an extensive set of experiments with it. The experiment results demonstrate that the proposed modification does achieve the three goals listed above over a broad set of parameters and problem sizes. As an example showcase, it is possible to solve certain instances using only 10% of the memory in less than twice as much time than the original F4 algorithm. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10392 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 數學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf | 1.21 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。