格的極值問(wèn)題的模形式算法及應(yīng)用研究.pdf

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

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