畢業(yè)論文：格基規(guī)約算法研究

1、目錄摘要iabstractiv第一章引言6課題的背景和意義6第二章格問題的研究72.1格問題的發(fā)展72.2格問題的算法發(fā)展72.2.1精確算法72.2.2近似算法82.3格問題的基礎(chǔ)知識92. 3.1低復(fù)雜度的格問題92. 3. 2高復(fù)雜度格問題9第三章 格基規(guī)約103.1格基的正交性103.2格基的規(guī)約103.3格基規(guī)約的基本定義和定理11第四章 格基規(guī)約算法134.1格基規(guī)約算法概述134.2 lll格基規(guī)約134.2.1基本定義134.2.2基本性質(zhì)144.3經(jīng)典的lll格基規(guī)約算法164.3.1低復(fù)雜度的lll格基規(guī)約算法164.3.2使用實(shí)例進(jìn)行實(shí)驗(yàn)204.3.3結(jié)果分析與結(jié)論214

2、.4遺傳算法實(shí)現(xiàn)格基規(guī)約的算法224. 4.1算法實(shí)現(xiàn)的概念224. 4.2遺傳算法的實(shí)質(zhì)224. 4. 3算法的步驟234.4.4實(shí)例的實(shí)驗(yàn)23第五章困難格問題的規(guī)約255.1高復(fù)雜度的格問題介紹255.2 ntl大數(shù)庫的介紹255. 3大數(shù)庫的使用265. 4幾種變種規(guī)約算法的介紹275.4. 1經(jīng)典lll算法：275.4. 2 lll-fp 算法275.4.3 bkz-fp 算法285.4.4 bkz-qp 算法285. 5高復(fù)雜度算法實(shí)現(xiàn)的原理285. 6實(shí)例測試305. 6.1低復(fù)雜度實(shí)例305.6.2高復(fù)雜度實(shí)例32第六章結(jié)論35參考文獻(xiàn)36致謝37附錄38格基規(guī)約算法研究摘要格是

3、數(shù)學(xué)上非常典型的一種線性代數(shù)結(jié)構(gòu)，而且格上一些問題的困難性已經(jīng) 得到了許多學(xué)者的證明。格的理論研究中的重點(diǎn)主要是集中在了格基規(guī)約上，這 同時也是密碼學(xué)中密碼系統(tǒng)的設(shè)計和分析中利用到格的一個重要工具。目前，在 格的理論研究中，許多格的問題均可以通過格基規(guī)約來進(jìn)行求解（因?yàn)槭莕p難 問題，一般都只能近似求解）。在實(shí)踐中，例如是在密碼體制的設(shè)計和密碼系統(tǒng) 的破解中，對一些密碼系統(tǒng)和密碼方案的分析其實(shí)在本質(zhì)上均可以等價成格基規(guī) 約問題。因此研究格基規(guī)約問題不僅具有很高的理論價值，而且具有重要的實(shí)用 價值。本文首先對格問題的背景和基礎(chǔ)知識進(jìn)行了學(xué)習(xí)和分析，然后研究了格中 的困難問題，最后重點(diǎn)研究了常見的

4、格基規(guī)約方法。研究了經(jīng)典的gram- schnorr 的厶厶厶經(jīng)典格基規(guī)約算法，用c+語言將該經(jīng)典算法實(shí)現(xiàn)，并用實(shí)例進(jìn)行試驗(yàn), 驗(yàn)證該算法的質(zhì)量。其次還用了遺傳算法來實(shí)現(xiàn)格基規(guī)約，并用相同實(shí)例，將得 到的結(jié)果進(jìn)行比較。論文的重點(diǎn)放在格的困難問題上，由于冃前計算機(jī)內(nèi)部數(shù)據(jù) 表示的一些局限性，使得大數(shù)的運(yùn)算和大數(shù)格的運(yùn)算稱為困難問題，本文使用了 ntl大數(shù)庫進(jìn)行輔助，在此基礎(chǔ)上，分別實(shí)現(xiàn)了經(jīng)典厶厶厶算法，lll-fp浮點(diǎn)算 法，bkz-fp分塊浮點(diǎn)算法，以及bkz-qp分塊四倍精度浮點(diǎn)算法，并使用相關(guān) 實(shí)例進(jìn)行實(shí)驗(yàn)，比較各算法的優(yōu)越性。關(guān)鍵詞：格；格基規(guī)約；lll； ntl大數(shù)庫abstractt

5、he lattice is mathematically a very typical of a linear algebraic structure, and the difficulty of some problems on the lattice has been proofed by many scholars the studying of lattice of theoretical mainly focused in the the lattice basis reduction, which is also an important tool at password syst

6、em designing and analysising in cryptography that can take advantage of of the lattice. in the theoretical study of the lattice problem, many of the lattice can be solved by linear reduction (usually only can be approximate with the solution). in practice, for example, in cryptosystem designing and

7、password cracking, the analysising of some of the password and password programs, in fact, are equivalented into lattice basis reduction the researching of lattice basis reduction do not only has a high theoretical value, but also has important practical value. in this peper, firstly, we present the

8、 background of lattice and the basic knowledge, the studying and analysising are focused on the difficult preblem of the lattice and then we study some basic definitions of the lattice and basis with quasi-orthogonal, as well as lattice basis reduction and the basic knowledge and basic theorems.we s

9、tudy the classic gram-schnorr lll classic algorithm and and validate the quality of the algorithm by using c + + with an examples to be tested secondly, we also use a genetic algorithm to achieve lattice basis reduction, and with the same instance we can compare the quaelity of the results. this pap

10、er focus on the difficult problem of the lattice.for some limitations of the data representation inside the computer so that making the large numbers computing and lattice computing of large numbers the difficult problem.in this article, with the using of the ntl library auxiliary, we validate the q

11、uality of the algorithm by using the classical lll algorithm lll-fp floating-point arithmetic, the bkz-fp block floating-point arithmetic, and the bkz-qp block quadruple precision floating-point arithmetic with some examples to experiment, we can see the comparison of the queality of all the algorit

12、hms.keywords: lattice, lll lattice basis reduction, ntl library第一章引言課題的背景和意義討論格問題的最早出現(xiàn)要回溯到19世紀(jì)，當(dāng)時的數(shù)論和密碼被研究了很長的 一段時間，那時候格在很多領(lǐng)域的應(yīng)用主要是負(fù)面的，例如格被用來破解各種密 碼系統(tǒng)。然而ajtai發(fā)表了他得里程碑式的論文，其利用格的難題來構(gòu)造新的密碼 系統(tǒng)的觀點(diǎn)讓許多的學(xué)者產(chǎn)牛了興趣。這個算法和格的相關(guān)的理論從此時才真正 的被開始應(yīng)用到密碼學(xué)的領(lǐng)域。在1990年，基于背包問題的密碼系統(tǒng)被lll的算 法攻破。這一成果展開了格理論在密碼分析學(xué)這一領(lǐng)域中的實(shí)際應(yīng)用，并且同時 更進(jìn)一

13、步的證明了 "單向函數(shù)假設(shè)”這一理論的不可靠性。1996年,在coppersmith 的論文中l(wèi)ll算法被提出來用于求解整系數(shù)同余方程（僅當(dāng)方程一定有足夠小的 解的時候）的算法。之后，coppersmith的這一方法被學(xué)者們廣泛的應(yīng)用于對rsa 密碼體制的部分密鑰泄露攻擊以及低指數(shù)攻擊等領(lǐng)域的應(yīng)用中。在近年來格在許多領(lǐng)域都己經(jīng)產(chǎn)牛積極的作用。在對格問題的研究基礎(chǔ)上， 人們設(shè)計出了基于格困難問題（np問題）的密碼系統(tǒng).shamir利用格基規(guī)約理論， 用lenstra的整數(shù)規(guī)劃算法成功破解了 merkle-hellman得基于背包問題的公鑰密 碼方案，其理論也被成功的用于加密指數(shù)為3的r

14、sa密碼方案的研究中，以及利 用其對ntru進(jìn)行分析和攻擊。密碼學(xué)界已經(jīng)認(rèn)定格問題是在計算困難問題吋的 新的源泉。除此之外，格的困難問題也可以用來設(shè)計公鑰密碼，可以用來抗量子 攻擊，如ntru密碼。這也是密碼學(xué)發(fā)展的一個新方向。第二章格問題的研究2.1格i可題的發(fā)展在1982年的時候，有三位偉大的數(shù)學(xué)家倫斯特拉(a.k.lenstra)，倫斯特 拉(h.w.lestm),洛伐茲(jr.l.lovasz)發(fā)明了厶厶厶算法。之后，厶厶厶算法被 許多學(xué)者視為是對解決np問題的一大突破，由于其簡明性和廣泛性的實(shí)際應(yīng)用, 很快被認(rèn)為是20世紀(jì)后期中最重要的理論算法成果之一.線性代數(shù)這一學(xué)科里 面的一些基

15、木理論表明：任何有限維歐氏空間都存在一個標(biāo)準(zhǔn)正交基，也就是說 每一個基都是由兩兩正交的單位矢量組成。那么，是否每一個格都是有標(biāo)準(zhǔn)正交 基的呢？然而，即使是對于2維格，也存在某種可能使得它不存在正交基。此時, 格基規(guī)約的目標(biāo)只能退而求其次。學(xué)者研究發(fā)現(xiàn)，對于任何一個格來說，總存在 這樣一個基，它離正交不遠(yuǎn)。(當(dāng)然，要精確定義什么是離正交不遠(yuǎn)也是需要某 種技巧的，截止到目前為止，我們只能說存在這樣一個基，它是由足夠短的格矢 量組成，這便意味著至少在幾何的意義上來說這樣的一些矢量相互之間是離正交 不遠(yuǎn)的)。世界上的第一個svp算法就是lagrange的規(guī)約算法，他使得該算法能夠在二 次方的時間內(nèi)解決

16、精確的二維svp。而對于任意維格，都是有兩類svp算法：精 確算法和近似算法。2.2格問題的算法發(fā)展2.2.1精確算法這些算法可證明找到一個最短矢量，但他們是開銷很大，運(yùn)行時間至少是維 數(shù)的指數(shù)次.木質(zhì)上，這些算法執(zhí)行一個窮舉搜索.精確算法可分成兩類：(1) 多項式空間精確算法.這些算法基于列舉法，但是由于不等式限制了搜索 的范圍，當(dāng)然也能找出所有長度小于m的非零的格的矢量。其中最好的具有確定 行的算法是kannan算法，該算法具有超過指數(shù)的最壞復(fù)雜度，其多項式運(yùn)算的 時間為/3呦。schnorr引用了pruning的技巧，將列舉法與分塊進(jìn)行規(guī)約兩者 相結(jié)合，事實(shí)上是在分塊的kz規(guī)約算法中加入

17、一個子過程，這個子過程是用列 舉算法實(shí)現(xiàn)的，由于該小技巧的使用，整個算法的實(shí)現(xiàn)速度上有了很大的提升。(2) 指數(shù)控件精確算法。在(1)的基礎(chǔ)上，這些算法會有更短的漸近的運(yùn)算時 間，可是還是有2的空間復(fù)雜度。在這類算法中最有代表性的是aks算法 (ajtai,kumar,sivakumar),這些算法即使在最壞的情況下起運(yùn)算時間也不會超過2心)。后來micciancio等人又提出了一個更加具有確定行的算法，該算法可以在 2如血的時間內(nèi)解決cvp與svp等問題。并且有多個aks的變形，其時間復(fù)雜度 達(dá)到2化2.2.2近似算法這類算法比精確算法實(shí)現(xiàn)的時間要短，最后輸出的結(jié)果保證是短的格矢量，但不一定

18、保證是最短的。該算法常輸出整個的規(guī)約基，所以我們稱之為格基規(guī)約7算法。該算法中最為著名的就是lenstra,lenstra, lovasz提出的厶厶厶算法，此算 法可以在多項式的時間復(fù)雜度內(nèi)解決近似因子是0(2/v3f)的svp問題，這個算 法本質(zhì)上就是hermite不等式的算法的變形。lll算法岀現(xiàn)后，研究的方向就集 中在兩個方面：(1) 更快的厶厶厶算法。這個方向致力于獲得在質(zhì)量類可以接受類似于或者是更 加差一點(diǎn)的厶厶厶規(guī)約基，當(dāng)然，它只需要更少的運(yùn)行吋間，這里面的方法是利用 的分治策略，或者是通過浮點(diǎn)算法也可以。因?yàn)楫?dāng)我們使用浮點(diǎn)數(shù)算術(shù)時，它可 以加快格基規(guī)約的速度，然而同吋也會帶來更多

19、大的浮點(diǎn)誤差，這些誤差很多時 候就會讓我們得到錯誤的結(jié)果，甚至使程序無法終止。因此，研究格基規(guī)約上的 浮點(diǎn)運(yùn)算的一些特性是非常有必要的。世界上首次得到正確的證明的浮點(diǎn)厶厶厶是 由schnoir提出來的，最近，一個比厶厶厶更加有效的浮點(diǎn)厶厶厶變形版是由nguyen 和stehle這兩位學(xué)者研究岀來的。但就目前來說，最為流行的版本還是基于啟發(fā) 式的浮點(diǎn)厶厶厶算法。盡管利用常規(guī)的方法就可以證明它的安全性，但是有的吋候 基于啟發(fā)式的算法會更加有效。1994年，一個非常重要的基于啟發(fā)式的算法由 schnorr和euchner提出來，一直延續(xù)到今天，這個基于啟發(fā)式的算法依i口是很多 浮點(diǎn)lll快速算法必不

20、可少的基礎(chǔ)。(2) 更強(qiáng)的lll算法。這種算法是以更長得運(yùn)行吋間為代價來獲得比厶厶厶算法 要更好更精確的近似因子。分塊的規(guī)約方法其本質(zhì)是在厶厶厶算法和hkz算法兩 者取得中間方法，令分塊的長度為d,參數(shù)力二1吋，分塊規(guī)約與hkz規(guī)約是等價 的；令分塊的長度d為2時，分塊kz規(guī)約就是變成了厶厶厶規(guī)約。目前最好的分塊 規(guī)約算法可以達(dá)到2°3唧。如他”)。不過這些算法在理論上沒有學(xué)者證明其最短矢 量界，并且它的吋間復(fù)雜度也有可能冋升亞指數(shù)的，不過這個算法在實(shí)際應(yīng)用中 能運(yùn)行得很好。之后gama和nguyen實(shí)現(xiàn)了三個算法：厶厶厶算法，深插入的厶厶厶算法，分塊 的kz規(guī)約算法，他們都是用nt

21、l庫實(shí)現(xiàn)的。而且實(shí)踐證明，深插入的厶厶厶算法 和分塊kz規(guī)約算法比厶厶厶算法的性能要好，口隨著分塊值朋勺增人，最終得到的 規(guī)約基的質(zhì)量就越好，當(dāng)然，運(yùn)行時間也增加了。綜上可以看出，更快和更高質(zhì)量這兩者之間是互補(bǔ)的，所有的精確算法首 先都需要用一個近似的算法（比如厶厶厶算法）來進(jìn)行預(yù)處理，其中所有的分塊算 法都需要調(diào)用大量的低維格的精確算法來作為子過程進(jìn)行處理。在實(shí)際中，大多 采用基于啟發(fā)式的算法，他們的運(yùn)行時間提升了許多，不過理論上很難被證明。 事實(shí)上，當(dāng)維數(shù)a2>150,能夠?qū)嵱玫闹挥薪扑惴?。最后，以前人們大都認(rèn)為格基規(guī)約算法的實(shí)際執(zhí)行的效率可以比學(xué)者們可證 明的理論界會更好。在上世

22、紀(jì)80年代末，格問題計算的復(fù)雜性程度引起了許多人 們的關(guān)注，主要是因?yàn)閍jtai發(fā)現(xiàn)了某種格的近似問題在最壞情況復(fù)雜度和平均情 況下的復(fù)雜度之間的相互聯(lián)系，這引起了理論密碼學(xué)家與計算機(jī)復(fù)雜度的領(lǐng)域?qū)?家的興趣。2.3格問題的基礎(chǔ)知識2. 3. 1低復(fù)雜度的格問題格是離散的疋加子群。每個格都是由一些線性無關(guān)的向量產(chǎn)生的集合，稱 之為基。任意格都有無數(shù)個基，格基規(guī)約是種在格的無數(shù)基中選擇這樣一個基 矢量：其長度盡可能小，并且與基中其他矢量盡可能正交。格基規(guī)約理論有著悠久的歷史，可以回溯到二次多項式的規(guī)約理論上。在7lenstra, lenstra和lovasz a個人的努力下，該工作達(dá)到了高峰，也

23、就是著名 的厶厶厶算法，它是第一個保證能夠計算出包含近似短向量的格的基的多項式時間 算法。此后，格基規(guī)約的方法有了進(jìn)一步的發(fā)展（例如，schnorr-euchner的格 基規(guī)約算法）并且在基礎(chǔ)數(shù)學(xué)和計算科學(xué)的許多領(lǐng)域該工作被認(rèn)為其價值是無可 估量的。特別是格理論的進(jìn)展使得想組合優(yōu)化和加密這些領(lǐng)域被徹底改革。例如, 格基規(guī)約理論技術(shù)已被用于攻擊截斷線性同余發(fā)生器，基于哈希散列函數(shù)的背包 問題以及像merkle-hellman公鑰密碼體制的密碼系統(tǒng)，rsa, ggh等。2. 3. 2高復(fù)雜度格問題然而，盡管在理論上取得了巨大的進(jìn)步，但是面向大型問題的實(shí)例，還是缺 少一般化的格基規(guī)約的方法。因此，在

24、實(shí)踐中去進(jìn)一步的進(jìn)行改善和提高理論技 術(shù)是非常重要的。在下面，我們提出了一種新的基于動態(tài)近似的啟發(fā)式算法，它 是為了提高改善schnorr-euchner的格基規(guī)約算法，也是在實(shí)踐中應(yīng)用最為廣泛 的一種格基規(guī)約算法。特別是這種新的啟發(fā)式算法在人型問題例子的分解以及在 例如用某些方法無法實(shí)現(xiàn)分解的問題上可以用我們提岀的新算法解決，這拓展了 schnoorr-euchner算法的適用性。第三章格基規(guī)約3.1格基的正交性設(shè)嘰也是n位歐式線性空間川中線性無關(guān)的向量，可以定義如下點(diǎn)集：l = 入也+希乞+. +易乞，4 wz,z = l,/我們稱之為格，并稱b、,.也為格的一個基，由于»6是線

25、性無關(guān)的，所以 任一個格的矢量x可以用一組基的線性組合來表示，而且這種表示方式肯定是 唯一，即有且僅有一種；但是如果x已經(jīng)在格中，并且能夠用以上的線性組合 的形式來表出，那么系數(shù)人,均為正數(shù)。任意格矢量均能被唯一表示為基矢量的線性組合。由于用基表出得格是有意 義的，格基本身就能用一個全為實(shí)數(shù)的系數(shù)矩陣來表示，因此我們可以非常方便 的使用電腦來表示任何一個格。如果從代數(shù)的角度來看，格則是由d個生成元組成的阿貝爾群，我們認(rèn)為 它是的子群。我們研究格問題的中心問題集中在shotrest vector problem （svp 問題），就是最短向量問題，它的定義如下：對于給定的一個格基b,要求找到 這

26、樣的一個非零的格的矢量，使得滿足一下條件：bxo,其長度要達(dá)到最小值 |&| =人。（其中長度被定義為歐幾里得長度）另一個集中點(diǎn)是closest vector problem（cvp問題），也就是最接近矢量問 題。該問題對于給定的目標(biāo)矢量和格基，要求找出最接近于該矢量的格點(diǎn)，即那 組基。兩個問題相比之下，cvp比svp要更加難以解決。因?yàn)榫_的svp問題 是屬于np問題，即多項式吋間困難問題，但它在實(shí)際中需要的地方并不多，所 以以下的近似svp問題被提岀。近似svp問題的定義為：給定秩為d的格l基b,近似因子為/ >1,要求 找出非零矢量uw厶，使得滿足以下條件：u </m

27、in |v , vg l0 o它可以簡單 記為apprsvpo截止到s前為止，已經(jīng)能夠證明apprsvp問題是np難得當(dāng)口僅 當(dāng)近似因子了 = 2噸尸。3.2格基的規(guī)約下面給出一些格基規(guī)約的相關(guān)概念：對任何矢量集sur”，span（s）是由s生成的線性空間，或者稱之為包含s的川的最小子空間。如果設(shè)ss”是格厶的一個格基，于是它的gram行列式可以表 示為（%./?）是d x斤階gram矩陣勺,巧）口加。關(guān)于gram行列式有一個很重要的在幾何學(xué)上的解釋，即當(dāng)»也線性無關(guān)，矢量b,.bd生成的平行多面體為：p（%.如二吃巧：（）n，/=1則©，乞）是該平行多而體的體積,可以記為

28、汰（.）。設(shè)坊（0,廠）= xw7?":卜v廠表示半徑是r中心在原點(diǎn)的斤維開球，簡記為b（0, r）。子空間eu r",它的止交補(bǔ)可以表示為£*丄=兀丘用：x,y=0,vy we。用 兀e ： r" t r"表示向量在e丄上的投影，那么當(dāng)xe e1時，7te（x） = x,當(dāng)x we時, 玉（兀）=0。當(dāng)厶u /?"是一個格，則l的秩被定義為span（l）的維數(shù)，當(dāng)刃=時格稱為 滿秩格。和川的線性子空間類似，格的基也補(bǔ)唯一。兩者的不同點(diǎn)集中在，不是所 有的最大線性無關(guān)矢量都能構(gòu)成一個基。任意一個格都有無數(shù)格基。設(shè)».恥疋為格

29、厶的某一個格基，矩陣任 意d個格矢量q,c2，c£l,矩陣為c,如果存在可逆的矩陣u滿足c = bu ,并 且|u| = ±1,那么 g,5也是格厶的一個基。顯然有無數(shù)格矩陣u滿足條件。設(shè)m ul是厶的子格，我們稱m是厶的本原子群，其中eur” ,且 m = lc氏同理，定義本源矢量九.如丘疋左61,要求該組矢量可以擴(kuò)充成厶 的一個基。這個svp問題一樣，每一個格都存在最短非零矢量，且不唯一。 minkowshi給出了最短非零矢量的長度的定義，其定義為格厶的第一最小值人。 又由于定義第二短矢量不具意義，所以minkowshi限定了最短矢量的定義為線性 無關(guān)的格矢量。3.3格

30、基規(guī)約的基本定義和定理定義3.1逐次最小值（the successive minima）格lb»的第廠個次最 小值定義為包含i格線性無關(guān)，且中心在原點(diǎn)的格矢量的最小求半徑4 （厶）=inf r: dimispanl b（0, r） >/ o定理3.1 （minkowski凸體定理）設(shè)lu r"是其可測凸集，并>1關(guān)于原點(diǎn)對 稱，且測度嚴(yán)格大于2%ol（l）,則c厶至少包含一個非零矢量。d!2推論3.1設(shè)lur”是一個d秩格，廿 為相應(yīng)的單位球的體積， "（d/2 + l）gamma函數(shù)可視為階乘函數(shù)在實(shí)數(shù)情況下的擴(kuò)展，則格厶包含一個非零矢量. 能滿足人

31、（厶）勻卜卜2（竺嚴(yán)）匕以上表達(dá)式可以用另一種方式來表示為人（厶）2/汰（厶嚴(yán)34/心嚴(yán),故 zj<4/（vjm,我們可以得出人的線性邊界人+彳。該值可以讓我們得到 人（厶）的上邊界。定理3.2 （minkowski第二定理）令厶u/?"是一個d秩格，則對于<y<d, 總滿足（匸；/（厶）"< yvol（l）/d o即是對于基為»點(diǎn)的格厶總有v/（l0）<nthii'當(dāng)其基的矢量相互正交 的時候，最終結(jié)果才能取等號。定義3.2 （正交虧損orthogonality defect）對于基是勺,，乞的格厶正交虧損 可以定義為厶）5

32、匸；：|刨/次（qa1,其中等號成立的條件為初始的格基為正 交基。綜上，格基規(guī)約的最終目的其實(shí)就是找到規(guī)約基，也就是由相當(dāng)短或者是 幾乎正交的格矢量組成的基。格基規(guī)約算法在數(shù)學(xué)和計算機(jī)，以及密碼學(xué)等許多 的領(lǐng)域具有非常高的研究價值。第四章格基規(guī)約算法4.1格基規(guī)約算法概述首先，取gn,且我們用制|表示列向量方的歐兒里得長度，用z 表示zwr中最接近的整數(shù)。整數(shù)格厶qz"的定義如下：厶=：兀q 丘乙,=1,.,沖，并且%閔，山wz"是線性無關(guān)的向量。我們稱，厶ez"x*是k階格l = l（b）的 一個基。格的基對于單模轉(zhuǎn)換來說是唯一的，比如說交換兩個基向量，基向量同

33、 乘以1,或是加某基向量的整數(shù)倍到另一基向量上。關(guān)于b匚的格lozm的行列式det（l）= det（byb）p ,其大小與基的選擇是無關(guān)的。b的虧缺被定義為學(xué)（3）det（£）nthll ° 通常妙如果b是一個正交基，則有勿（3） = 1。通過改進(jìn)格的基的規(guī)約方式這個誤差是可以 被減小的，通過這種方式來構(gòu)建出格中許多基中的一個基，這個基向量是盡量小 的（通過歐幾里得長度來衡量），并且與其他的基之間是盡量正交化的。下面要 提到的所謂厶厶厶規(guī)約就是最為著名的格基規(guī)約中的一種方法。4.2 lll格基規(guī)約 4.2.1基本定義定義3.3對于基b = （b,.,bjwz她的格它符合gr

34、am-chmidt正交 化后的丘0"“，并且其gram-schmidt系數(shù)表示為（其中 <j<i<k）,如果下面的條件也滿足的話，則我們稱基b為厶厶厶規(guī)約的：a.|<1（1 <</</:） （1）23.20： +他di| 訂|0二| ,（w）（2）第一個性質(zhì)是規(guī)約的規(guī)則。其中（2）里的恒定因子2就是所謂的規(guī)約系數(shù),4這個系數(shù)可以被任何一個固定的實(shí)數(shù)y代替，其屮丄<）yl。4該lll格基規(guī)約算法的質(zhì)量，即是得到的格的基向量的止交化程度和長度 的大小，這些可以被如下定理進(jìn)行量化:定理3.3令厶wzz"為一個格，而b =wz她為厶的

35、一個厶厶厶規(guī)約基。則如下估計成立：|刖|劃 s2*twdet(d(3)|也3 2鋼»,咗厶，心0(4)定義3.4 (矢量的歐兒里德長度)對于維矢量v = v1,v2,.,vwt(v/ wz,z = l,.,n)的長度(euclidean norm)制| 定義為|卜：=工詳。/=1定義3.5 (連續(xù)最小值)在歐幾里德長度定義的基礎(chǔ)上，我們定義斤維格厶 的一組基礎(chǔ)性的常數(shù)值(successive minima) &(厶)，,&(厶):可以包含格厶中，個 線性無關(guān)的向量的最小的圓的半徑。其實(shí)質(zhì)就是不小于i個線性無關(guān)的向量的歐 兒里德長度的最小值。4.2.2基本性質(zhì)定理3.4

36、 (minkowski定理)對階格厶的所有基屮最短向量:的長度人有：_丄人 <vndet(l)n且對于格厶的連續(xù)最小值人，心1,.加有：n11(口如” < 麗det(d"i=lminkowski規(guī)約基可能存在，但并不是任何格均存在minkowski規(guī)約基。 其中det(£):= fllmi < det(l)i=其中巧是對片進(jìn)行smicher正交化得到的。定義3.6 (korkinezolotareff規(guī)約基)即kz規(guī)約基：若格厶上的一組基 %優(yōu),，4，, = 1,2,.,滿足2腳| =人(厶),心1,兀就稱之為也為kz規(guī)約基。gram-schmidt正交化

37、：該過程即是將一組有序的基投影到相互垂直的基上。 若將正交向量構(gòu)成的ji實(shí)數(shù)空間看成是超平面的p(b；,b；,.,b；j, 則第j個基向量勺的gram-schmidt je交化就是將勺朝超平面p(b；,b；,上投 影，于是得到兩個分量：好和±u*b；。使好替換勺。因?yàn)?quot;與超平而圖4.1關(guān)于格基規(guī)約算法還有以下命題：設(shè)0 = 嶺°2，,匕是格厶的一個基，且0、咕町，叮是經(jīng)過gram-schmidt正交化后的基。貝【jdet(l) = w?/(f)< |v! | v2 .匕，det(l) = n|v；|其證明如下：設(shè)f = f(vpv2,.,vj和f二f(&qu

38、ot;，k，叮)分別是初始格基向量和進(jìn)行g(shù)ram-schmidt變換后的基構(gòu)成的矩陣。則有m=f，其中100 00“2,110 00“3,1r“3.2r1 00tr n-1.3 f10v卩叫2卩仇,3卩仇一1.71r1丿圖4.2且 det(l) = |det f = |det(mf*)| = |(det(m)(det(f*)| = |det(f*)| = pj|v*|。i=l定義3.7設(shè)0 = 訃,是格厶的一個基,且是經(jīng)過gram-schmidt正交化后的基?；胺Q為lll規(guī)約的，當(dāng)且僅當(dāng)滿足下列兩個條件：v. - v,*1(1 )即是大小條件，坷j = < ,(1 < j <

39、;i< n) '忙| 2(2 )即是 lovasz 條件，» » (才-u：j |”二,(1 < z < n)口規(guī)約基的初始基滿足：陋卜2"嘰|det(d|"" o4.3經(jīng)典的lll格基規(guī)約算法 4.3.1低復(fù)雜度的lll格基規(guī)約算法下面就給岀格基規(guī)約算法低復(fù)雜度的格基規(guī)約算法。這個算法將給定的格的基轉(zhuǎn)換為lll規(guī)約基，其工作原理如下：算法 1： lll(b,.,bj輸入：一個格的基8 = 0,0)wz"“輸出：厶厶厶規(guī)約基77(1) 計算b;-(即各個基的長度的平方)和相應(yīng)的“，廠當(dāng)1 < j <

40、;i<ki,使用 gram-schmidt 方法(2) l:=2(3) while(/</c) do(4) reduce(如)(5) if(財v弓-“為)|慎)then(6) swap如，勺)(7) i:=max/-l,2|(8) else(9) for(m:= l-2;m> 1;m)do(10) reduce(“加)(11) end do(12) /:=/ + l(13) end if(14) end do用子程序swap勺)來交換兩個基向量勺一和勺，而子程序reduce (如)被用來規(guī)約縮小因子如，以達(dá)到% 5 *的目的。對于任何有基b = ©,$) g的格厶u

41、 z”，該基b的厶厶厶規(guī)約基都可以 在多項式時間內(nèi)計算出來。更確切的說，該算法運(yùn)算執(zhí)行的時間大小為 ?；飐logc),運(yùn)算中個的這個整數(shù)的長度用2進(jìn)制表示的大小為o(klogc)執(zhí)行, 其中 ce/?,c> 2,|血< c,其 +l<z<ko光從理論的角度上來看，盡管該算法運(yùn)算起來有不錯的性能和很好的表現(xiàn)， 但在實(shí)踐中基本上是無用的，為了保證在基中不發(fā)生什么錯誤，所以用于精確的 長整數(shù)運(yùn)算的子程序必須被使用，而該子程序運(yùn)行太過緩慢(因而可以改變格)oschnorr和euchner取得了這種情況下的第一個重大改進(jìn)(因而使得在實(shí)踐 中使用厶厶厶規(guī)約算法成為可能),他們使用了

42、快速浮點(diǎn)算法和gram-schmidt系 數(shù)地來計算以得到整數(shù)格的近似解，從而重寫了原厶厶厶算法，然而其他的算法 都是通過使用確切的整數(shù)算法來計算的。此外，前面己經(jīng)介紹過的為了避免和修 正浮點(diǎn)算法中的錯誤的啟發(fā)式算法，它在原始的厶厶厶算法的基礎(chǔ)上提供了一種實(shí) 際并且合理的變種算法，并且具有很好的穩(wěn)定性。算法 2.schnorr-euchner (% ，儀)輸入:一個格的基b = (»,bjwz血輸出：厶厶厶算法規(guī)約基(1) 1:=2(2) f := false(3) fr := false(4) approx.basis(5) while(/<k) do(6) for(m:=

43、2;+) do(7) orthogonalize(m)(8) end do(9) for(m:=/-l;m> 1 )do(10) reduce(如)(11) end do(12) if(巧.=true)then(13) approx_vector(bb);(14) fr = false(15) end if(16) if(fr=true)(17) z:=max/-1,2(18) fc := false(19) else(20) if(3<(：-扇粘)4(21) swap®.】,勺)(22) i :=max(/-l,2(23) else(24) /:=/ + l(25) e

44、nd if(26) end 訐(27) end do給定格b的每個基b在子程序approx basis和approx vector的調(diào) 用下分別向b逼近，并且是使用浮點(diǎn)運(yùn)算，即一個近似的但是快速的數(shù)據(jù)類型。 由于穩(wěn)定的原因，和兩個子程序0rthogonalize (用于計算gram-schmidt 正交化過程)和reduce (用于計算規(guī)約過程)一樣，主要算法中為了減小浮 點(diǎn)錯誤的啟發(fā)式算法是允許的。算法 3： orthogonalize 2輸入：z,(l<z </:),$向量q,0和勺：,», p,(1 << p </), b.=，(1<7<

45、;02輸出：bj = b； (1) 坊=|"(2) for(j:= 1;j<z-1;y + 4-)(3) if(臨；婦卜2習(xí)唧”畀)then(4) s = approx厶ue眼b(5) else(6) $ =他嗎)(7) end if(8) 珀円屮(9) b嚴(yán) bj-此bj(10) end do(11) 心算法 4： reduce%)輸入：旳，出，弧，(l<t? <7,=1)輸出：e，如，fc，f,其中(闖呂,1"")(1) if(|“>*) then(2) ft := tnie(3) if(比j > 22) then(4) fc :

46、= true(5) end if(6) s := bt. - f 比bj伽(q：=；q5j；q + +) do hg：=他一“j pjq end do(10) end if4.3.2使用實(shí)例進(jìn)行實(shí)驗(yàn)陣中的數(shù)值均為實(shí)數(shù)，且均為整數(shù)。下面給出一個小的實(shí)例進(jìn)行演示，初始輸入的格m是一個6x6的矩陣，矩 輸入矩陣如下：19232463331542110324431502441620444401815048351631314833329129m =程序運(yùn)行截圖如下:請 f:graduation thesisdebugmain.exe摘入列菱232 46333154211 0324150 24416|20

47、4444 01815|0 4835 1631313332 9129圖4.3程序運(yùn)行結(jié)果截圖如下:97 -12 -833241611 00 2444 033418 1531 311 2919154320轆入仃數(shù)6 輸入列數(shù)北2 32 464215440 48 35 1648 33 32416 1315 -9-7 -20 -21 -24 21 -15 -9 -11 1 3119 916-205 2 _6 -107 4det<m>=777406251det<m>=777406251h<tt>=0.46908h<mlll>-0.88824press an

48、y key to continue8 -12 _6 -11圖4.44.3.3結(jié)果分析與結(jié)論經(jīng)過規(guī)約后的基為:7-12-84199-204-91613165233015-9-6-7-20-218-12-10-2421-15-6-1174-9-11131其中，初始基和經(jīng)過規(guī)約后的基的行列式和同：det(m) = det(mlll) = ±777406251 哈德蒙德比率變化如下：h(m) = 0.46908h(m) = 0.88824即最終得到的最短矢量為(7,12,8,4,19,9),規(guī)約前的基的最短矢量長度為 |=67.85,而眉| = 26.74,和精確的最短矢量長度26.062相

49、差不算太大。顯然，不論是運(yùn)行的時間還是這個schonorr-euchner算法的穩(wěn)定性都是強(qiáng)烈 的依賴于使用的近似值的精確度。雖然高精度的近似意味著效率上的重大損失， 但是如果精度太低，由于(累積的)浮點(diǎn)錯誤，雖然不會導(dǎo)致程序終止，但是會 讓程序進(jìn)入死循環(huán)。因此，該算法任然缺乏效率，特別是對于大的格基或者大的 輸入基，因?yàn)楸仨毷褂酶呔鹊慕浦?。為了克服這個問題，我們將在下面介紹 一種新的啟發(fā)式算法，這種算法允許浮點(diǎn)精度的動態(tài)適應(yīng)，因此可以大大的減小 相應(yīng)的規(guī)約過程的運(yùn)行時間。4.4遺傳算法實(shí)現(xiàn)格基規(guī)約的算法4. 4. 1算法實(shí)現(xiàn)的概念模式:模式表示基因串中某些特征位置相同的結(jié)構(gòu)，它描述的是一

50、個串的 子集，在二進(jìn)制編碼的串中，模式是基于三個字符集(0,1, *)的字符串，符號 勺弋表任意字符，即0或1。對于二進(jìn)制編碼串，當(dāng)串長為/時，共有3個不同的 模式，遺傳算法中串的運(yùn)算實(shí)際上是模式的運(yùn)算。模式階：模式h中確定位置的個數(shù)稱為模式h的模式階，記作0(h),如o (101*1*1)二5。模式階用來反映不同模式之間的確定性差異，模式階數(shù)越低， 模式的確定性越低，所匹配的樣本個數(shù)就越多。定義距：模式h中第一個確定位置和最后一個確定位置之間的距離稱為模式的 定義距，記作5(h)。如5(100*1*) = 4。在遺傳操作中，即使階數(shù)相同的模式也會有不同的性質(zhì)，定義距就反映了這 種性質(zhì)的差異。

51、模式定理：在遺傳算法選擇、交叉、變異算子的作用下，具有低階、短定義距以 及平均適應(yīng)度值高于種群品均適應(yīng)度值的模式在子代中成指數(shù)增長。模式定理的 數(shù)學(xué)公式表不為 mh/+ 1 m t 丁 .) p o h pm(2-1)式中，加(h,/ + l)表示在t+1代種群車存在模式h的個體數(shù)目；m( h, t表示在t代種群中存在模式h的個體數(shù)目；f(h)表示在t代種群中包含模式h的個體平均適應(yīng)度；f表示在t代種群中所有個體的平均適應(yīng)度；i表示個體的長度；幾表示交叉概率;pm表示變異概率。模式定理是遺傳算法的基本理論，保證了較優(yōu)的模式(遺傳算法的較優(yōu)解) 的數(shù)目呈指數(shù)增長，為解釋遺傳算法的機(jī)理提供了一種數(shù)

52、學(xué)工具。4. 4.2遺傳算法的實(shí)質(zhì)傳統(tǒng)的優(yōu)化方法主要有3種：枚舉法、啟發(fā)式算法、和搜索算法，本文用到 的是第一中優(yōu)化方法，即枚舉法。由于格基規(guī)約的過程等價于是找到輸入格的一 個最短基，這設(shè)計到線性代數(shù)里面的線性空間，其實(shí)就等于對輸入格進(jìn)行初等變 換，將所有初等變換后的基的長度運(yùn)算出來統(tǒng)計，并得出歐幾里德長度最短的那 個向量，就是最終得到的那個向量。唯一的問題在于變換的次數(shù)，即枚舉的個數(shù), 這里，可以進(jìn)行自己設(shè)定枚舉的次數(shù)。由于該算法在進(jìn)行初等變化的時候是隨機(jī)進(jìn)行的，所以，從概率學(xué)的角度上來說，一般都是枚舉次數(shù)越多，最終的結(jié)果越 精確。4. 4. 3算法的步驟步驟如下：（1 ）設(shè) 方，,匕）為起

53、始格基，并且相互之間是線性無關(guān)的。（2 ）令e為單位矩陣（hx川階），對e做三類初等變換，某行（列）乘以某數(shù)，某兩行 （列）相互交換，某行（列）加到另一行（列）上去。令初等變換后的單位矩陣為a。（3）令w = axv ,其中v=（vp.,vzz） , w =（w,，叫），求出（w,w“），并計算其 中最短的那個向量及其長度。（4 ）循環(huán)2,3兩個步驟n次，比較每次求出來的最短矢量的長度，從中找出長度最小的464444833320得到的最短向量為-13 -8 4 20 9 歐幾里德長度為： press any key to29:28.178 continue矢量，即為要求的格最短矢量。4.4.4

54、實(shí)例的實(shí)驗(yàn)如下，輸入的格基為：1923246333_15421103244315024416m =20444401815048351631314833329129程序運(yùn)行如下：r-f:graduation thesisyichuandebugyichuan.exe"1 ° 1 ® 1 s菲i|圖4.5可以看到，和上一節(jié)輸入的基相同，但最終出來的結(jié)果顯示要比厶厶厶經(jīng)典算法的結(jié)果要長，這里得到的基的長度為28.178,而厶厶厶經(jīng)典算法的長度為26.74,0 這是枚舉了 100次后運(yùn)行的結(jié)果?？梢钥闯?，遺傳算法和厶厶厶相比較，一般說來, 厶厶厶經(jīng)典算法得到的結(jié)果要更為精

55、確,這是由于遺傳算法算法木身的存在的隨機(jī) 性所決定的。第五章困難格問題的規(guī)約5. 1高復(fù)雜度的格問題介紹高復(fù)雜度的格基規(guī)約算法指的是高復(fù)雜度的np問題，第一是初始輸入的格 基的維數(shù)較大，一般從幾十到幾千不等，所以運(yùn)行的時間無法估量；第二是初 始輸入的格基內(nèi)部各元素木身就是大數(shù)，這些大數(shù)的位數(shù)也是從幾十到幾百位之 間，大多超出了一般個人計算機(jī)的表示范圍，因?yàn)楝F(xiàn)有的個人計算機(jī)一般都是 32位機(jī)，或者是64位機(jī)，其能表達(dá)的數(shù)值的位數(shù)最多也只能達(dá)到32位和64位。 所以高復(fù)雜度的格基規(guī)約算法要解決的問題有很多，集中的問題在以下幾點(diǎn)：(1 )計算機(jī)內(nèi)部應(yīng)該如何表示這些位數(shù)較長的大數(shù)(2) 如何定義這些大

56、數(shù)之間的加減乘除等四則運(yùn)算(3) 如何實(shí)現(xiàn)大型矩陣間的表示和運(yùn)算鑒于以上提出的三點(diǎn)問題，可以使用microsoft公司研發(fā)的ntl大數(shù)庫來解 決。5.2 ntl大數(shù)庫的介紹下面首先將對該大數(shù)庫進(jìn)行簡單的介紹：ntl庫是一個高性能的，并且可以直接移植到c+中的大數(shù)庫。它可以提 供任意長度的整數(shù)的數(shù)據(jù)結(jié)構(gòu)和運(yùn)算，例如向量，矩陣，整數(shù)，多項式和有限域 的運(yùn)算，以及任意精度的浮點(diǎn)運(yùn)算。由于ntl大數(shù)庫提供了非常優(yōu)異的大數(shù)運(yùn)算，這讓我們無需討論其大數(shù)運(yùn) 算在計算機(jī)內(nèi)部實(shí)現(xiàn)的細(xì)節(jié)，可以直接把ntl大數(shù)庫當(dāng)成是解決高復(fù)雜度格基 規(guī)約問題的一個非常有力的工具。ntl是一種可以移植的c + +數(shù)論庫，該庫提供的數(shù)據(jù)結(jié)構(gòu)和算法，在 各種大數(shù)庫屮性能較高。ntl主要應(yīng)用