Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10807
Title: | 解佈於二元體之多項式方程組之快速窮舉法 Fast Exhaustive Search for Polynomial Systems over F2 |
Authors: | Tung Chou 周彤 |
Advisor: | 鄭振牟 |
Keyword: | 顯示卡,代數攻擊,多變量密碼學,窮舉搜尋,平行化, algebraic cryptanalysis,multivariate cryptography,multivariate polynomials,solving systems of equations,exhaustive search,parallelization,CUDA,Graphic Processing Units (GPUs), |
Publication Year : | 2010 |
Degree: | 碩士 |
Abstract: | 解多變量系統的問題在許多領域,包含代數攻擊和多變量密碼學,都具有重要的地位。然而,現存的演算法如 F4/F5 和 XL 雖然對於具有某些特性的系統效果特別顯著,但在面對一般的系統時,通常都無法有效率地解決問題,甚至會帶來嚴重的記憶體匱乏的問題。
基於上述的理由,我們便開始尋求另一個適合一般系統的解決方案,也就是窮舉搜尋 (exhaustive search) 的方式。在這篇論文中,我們提出並深入研究了一個窮舉搜尋的演算法 GGCE (generalized Gray code enumeration),用以解佈於二元體的多項式系統。這個演算法不僅相當易於平行化,對於解低次數的系統也有非常好的表現。對於這個演算法理論上的效能和記憶體需求等重要議題,在之後也會有深入的分析。 以實際面而言,我們將 GGCE 實作於顯示卡及 CPU 上。經過適當的最佳化之後,我們發現 GGCE 不僅在理論上相當有效率,實際的表現甚至遠勝過現有的演算法。換句話說,在面對一般系統時,窮舉搜尋可能是最好的解法。 簡而言之,我們提出了一個不同於以往的策略來解多變量系統。GGCE 證明了窮舉搜尋本身的強大能力,對於需要解多變量系統的眾多領域,勢必也會產生相當的影響。 |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10807 |
Fulltext Rights: | 同意授權(全球公開) |
Appears in Collections: | 電機工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-99-1.pdf | 449.61 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.