格的極值問題的模形式算法及應用研究.pdf

1、格問題在現在的公鑰加密方案中扮演了相當重要的角色，格問題的計算難解性為許多創(chuàng)新性的公鑰加密方案提供了理論依據。模形式算法作為新的隨機算法解決歐幾里得空間內的最短格向量(SVP)和最近格向量(CVP)問題。利用此方法，不僅可以求SVP和CVP的最小的格向量的非零2-范數的值，同時還可以求出滿足要求的最小格向量的個數。模形式方法主要基于格向量的2-范數的母函數和西塔函數的特殊性質。從計算復雜性的觀點來看，以解決格向量問題的SVP問題為例，在

2、所有以維度dim(Λn)=n階hn=l(Λn)的整數格向量范圍內，算法能夠以（1-ε）的可能性找到最小的非零格向量同時計算出滿足條件的最小非零格向量的個數，時間復雜度為(loglog(n2hn)）O(n)log(1/ε)，空間復雜度為n的多項式復雜度。確切的說，影響時間復雜度最大的因素來源于模形式算法需要獨立的隨機抽取格向量(loglog(n2hn)）O(n)log(1/ε)次，其余的所有的操作對于算法復雜度的影響只是n的多項式復雜度。