電機資訊學院: 電子工程學研究所指導教授: 鄭振牟王偉政Wang, Wei-JengWei-JengWang2017-03-062018-07-102017-03-062018-07-102016http://ntur.lib.ntu.edu.tw//handle/246246/276506在密碼學的領域裡，如何在有限體裡面解多變量方程組是一個很重要的問題。我們已經知道在F2裡且低維度的系統下，當變數與方程式的數量一樣多時，列舉演算法比現存的任何演算法都還要有效率，當然，我們只考慮實際可能的問題大小。然而我們卻不知道對於其他有限體是否也有一樣的結果。 因此，在此研究中我們對於在F3裡維度較低的系統提出了適合平行化的窮舉搜尋演算法，這個演算法不僅可以透過SSE2指令集使的在CPU達到平行化的效果，也可以經由CUDA實作在顯示晶片上。它的優化技巧以及與F2演算法的差異我們也會詳加分析。 我們的實作在使用了nVidia顯示卡時，解維度2、變數30且方程式30+的多變量系統問題只需要14分鐘；此外，解維度3的系統可以在36分鐘內完成。這些表現也都超越了所有現存的演算法，同時根據這些結果我們可以進一步的比較隨著有限體的大小增加，Gröbner基底與列舉演算法之間的關係。Solving multivariate polynomial systems over finite fields is an important problem in cryptography. For random F2 low-degree systems with equally many variables and equations, enumeration is more efficient than advanced solvers for all practical problem sizes. Whether there are others remained an open problem. We here study and propose an exhaustive-search algorithm for low-degree systems over F3 which is suitable for parallelization. We implemented it on Graphic Processing Units (GPUs) and commodity CPUs. Its optimizations and differences from the F2 case are also analyzed. We can solve 30+ quadratic equations in 30 variables on an NVIDIA GeForce GTX 980 Ti in 14 minutes; a cubic system takes 36 minutes. This well outperforms existing solvers. Using these results, we compare Gröbner Bases vs. enumeration for polynomial systems over small fields as the sizes go up.1496904 bytesapplication/pdf論文公開時間: 2016/8/2論文使用權限: 同意有償授權(權利金給回饋學校)多變量方程式代數分析窮舉搜尋平行化顯示晶片multivariate polynomialalgebraic cryptanalysisexhaustive searchparallelizationGraphic Processing Units (GPUs)thesis10.6342/NTU201601453http://ntur.lib.ntu.edu.tw/bitstream/246246/276506/1/ntu-105-R03943100-1.pdf