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

1、I目錄摘要................................................................................................................................................IAbstract..............................................................

2、...............................................................................II第一章引言..................................................................................................................................3課題的

3、背景和意義....................................................................................................................3第二章格問題的研究.........................................................................................

4、.............................42.1格問題的發(fā)展....................................................................................................................42.2格問題的算法發(fā)展.....................................................

5、.....................................................42.2.1精確算法.................................................................................................................42.2.2近似算法..................................

6、...............................................................................52.3格問題的基礎知識.............................................................................................................62.3.1低復雜度的格問題......

7、...........................................................................................62.3.2高復雜度格問題.....................................................................................................6第三章格基規(guī)約.......

8、.............................................................................................................73.1格基的正交性.....................................................................................................

9、................73.2格基的規(guī)約.........................................................................................................................73.3格基規(guī)約的基本定義和定理..........................................................

10、...................................8第四章格基規(guī)約算法.......................................................................................................104.1格基規(guī)約算法概述...........................................................

11、................................................104.2LLL格基規(guī)約...................................................................................................................104.2.1基本定義..................................

12、.............................................................................104.2.2基本性質...............................................................................................................114.3經(jīng)典的LLL格基規(guī)約算法....

13、....................................................................................134.3.1低復雜度的LLL格基規(guī)約算法........................................................................134.3.2使用實例進行實驗............................

14、....................................................................174.3.3結果分析與結論....................................................................................................184.4遺傳算法實現(xiàn)格基規(guī)約的算法....................

15、............................................................194.4.1算法實現(xiàn)的概念...................................................................................................194.4.2遺傳算法的實質.................................

16、.................................................................194.4.3算法的步驟...........................................................................................................204.4.4實例的實驗........................

17、..................................................................................20第五章困難格問題的規(guī)約............................................................................................................225.1高復雜度的格問題介紹..

18、.................................................................................................225.2NTL大數(shù)庫的介紹...........................................................................................................22

19、5.3大數(shù)庫的使用...................................................................................................................235.4幾種變種規(guī)約算法的介紹................................................................................

20、...............245.4.1經(jīng)典LLL算法：...................................................................................................245.4.2LLLFP算法.............................................................................

21、............................245.4.3BKZFP算法.........................................................................................................255.4.4BKZQP算法...........................................................

22、..............................................255.5高復雜度算法實現(xiàn)的原理...............................................................................................255.6實例測試......................................................

23、.....................................................................275.6.1低復雜度實例.......................................................................................................27III格基規(guī)約算法研究摘要格是數(shù)學上非常典型的一種線性代數(shù)結構，而

24、且格上一些問題的困難性已經(jīng)得到了許多學者的證明。格的理論研究中的重點主要是集中在了格基規(guī)約上，這同時也是密碼學中密碼系統(tǒng)的設計和分析中利用到格的一個重要工具。目前，在格的理論研究中，許多格的問題均可以通過格基規(guī)約來進行求解（因為是NP難問題，一般都只能近似求解）。在實踐中，例如是在密碼體制的設計和密碼系統(tǒng)的破解中，對一些密碼系統(tǒng)和密碼方案的分析其實在本質上均可以等價成格基規(guī)約問題。因此研究格基規(guī)約問題不僅具有很高的理論價值，而且具有重要

25、的實用價值。本文首先對格問題的背景和基礎知識進行了學習和分析，然后研究了格中的困難問題，最后重點研究了常見的格基規(guī)約方法。研究了經(jīng)典的GramSchnr的經(jīng)典格基規(guī)約算法，用C語言將該經(jīng)典算法實現(xiàn)，并用LLL實例進行試驗，驗證該算法的質量。其次還用了遺傳算法來實現(xiàn)格基規(guī)約，并用相同實例，將得到的結果進行比較。論文的重點放在格的困難問題上，由于目前計算機內(nèi)部數(shù)據(jù)表示的一些局限性，使得大數(shù)的運算和大數(shù)格的運算稱為困難問題，本文使用了NTL大