本文關鍵詞：格理論中計算格基和格基約化問題研究，由筆耕文化傳播整理發(fā)布。

【摘要】：這篇論文旨在研究格理論中兩個非常基礎又非常重要的計算問題:計算格基問題和格基約化問題.計算格基問題指的是給定一組格生成元,計算它們生成的格的一組基.格基約化問題則是給定一組格基,計算出具有某種較好性質的格基,或者是向量長度較短,或者是局部向量張成的體積較小等.這兩個計算問題關系密切,互為交叉:計算格基是進行格基約化的前提;格基約化過程的局部處理常常涉及計算格基,而且格基約化方法經(jīng)過適當?shù)男拚材苡脕碛嬎愀窕?兩者作為基本問題有著重要和廣泛的應用.例如,計算格基算法可以用來確定代數(shù)數(shù)域中的基本單位元,格基約化算法是密碼分析的重要工具.因此,研究這兩個問題的理論價值和實際意義不言而喻.本文的第一項工作是較為系統(tǒng)地研究了計算格基算法.先前的計算格基算法中,具有線性輸出基的算法不具有擬線性時間復雜性,而具有擬線性時間復雜性的算法不具有線性輸出基.我們通過引入Euclid交換、正則系統(tǒng)、松弛約化和按塊交換等新的技術和想法,首次給出了一個同時具有線性輸出基和時間復雜性關于log‖B0‖擬線性的計算格基算法,并且在標準算術下復雜性是O(mn4(log n+log‖B0‖)2),其中B0∈Zm×n表示輸入的格生成元.我們進而給出了具有線性輸出基和擬線性時間復雜性的本原向量組格基擴充算法.本文的第二項工作是探討了滑動約化基的性質.作為當前理論上最好的近似求解最短向量問題的格基約化算法,Gama-Nguyen滑動約化算法被視為著名的Mordell不等式的算法實現(xiàn).通過推廣先前的證明方法,我們推導了Gama-Nguyen滑動約化基與逐次極小值之間的比例關系,從而對該類型基的約化程度給出了更全面的刻劃.本文的第三項工作是給出了一個近似求解最小體積問題的格基約化算法.我們證明了一個新的關于Rankin常數(shù)的不等式,該不等式用低維Rankin常數(shù)γk,r給出高維Rankin常數(shù)γn,r的上界.通過推廣先前的約化概念,我們給出了輸出因子對應上述新Rankin不等式的一個格基約化算法.該算法能確定性地在多項式時間內近似求解最小體積問題.這一項工作可以看成是經(jīng)典的Mordell不等式和Gama-Nguyen滑動約化算法的延續(xù).
【關鍵詞】：計算格基 格基約化 最短向量問題 最小體積問題 擬線性算法
【學位授予單位】：清華大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：O153.1
【目錄】：

• 摘要3-4
• Abstract4-8
• 主要符號對照表8-9
• 第1章 緒論9-20
• 1.1 選題背景和意義9-11
• 1.2 國內外研究現(xiàn)狀11-18
• 1.2.1 計算格基算法11-13
• 1.2.2 格基約化算法13-18
• 1.3 本文結構安排18-20
• 第2章 預備知識20-29
• 2.1 格基本知識20-28
• 2.1.1 格定義20-21
• 2.1.2 對偶格21-23
• 2.1.3 逐次極小值23-24
• 2.1.4 Hermite常數(shù)和Rankin常數(shù)24-27
• 2.1.5 二次型27-28
• 2.2 復雜性模型28-29
• 第3章 Gram-Schmidt正交化和LLL算法回顧29-40
• 3.1 Gram-Schmidt正交化29-34
• 3.1.1 相關GSO量31-32
• 3.1.2 整型GSO量32-34
• 3.2 尺寸約化34-35
• 3.3 LLL算法35-40
• 3.3.1 LLL約化的定義和性質35-36
• 3.3.2 LLL算法及其復雜性分析36-40
• 第4章 計算格基算法40-66
• 4.1 Pohst修正型LLL算法40-43
• 4.2 基于Pohst MLLL框架的優(yōu)化算法43-45
• 4.3 基于XGCD的擬線性算法45-48
• 4.3.1 Euclid交換45-46
• 4.3.2 基于XGCD的擬線性算法46-48
• 4.4 基于按塊交換的擬線性算法48-61
• 4.4.1 松弛約化48-52
• 4.4.2 混合松弛約化的按塊交換程序52-58
• 4.4.3 基于按塊交換的擬線性算法58-61
• 4.5 應用: 本原向量組的格基擴充61-66
• 第5章 近似求解SVP算法66-79
• 5.1 一些基本約化概念66-67
• 5.2 Gama-Nguyen滑動約化的定義和性質67-69
• 5.2.1 Mordell不等式的經(jīng)典證明67
• 5.2.2 Gama-Nguyen滑動約化的定義和性質67-69
• 5.3 Gama-Nguyen滑動約化基與逐次極小值的關系69-74
• 5.3.1 定理 5.5 的證明70-74
• 5.4 Gama-Nguyen滑動約化算法74-79
• 第6章 近似求解DSP算法  按塊Rankin約化算法79-90
• 6.1 關于Rankin常數(shù)的新不等式80-82
• 6.1.1 定理 6.1 的證明80-81
• 6.1.2 定理 6.1 的算法含義81-82
• 6.2 按塊Rankin約化的定義和性質82-85
• 6.3 按塊Rankin約化算法85-88
• 6.4 復雜性分析88-90
• 第7章 結論90-92
• 參考文獻92-98
• 附錄A 三個技術性引理98-100
• 附錄B 按塊Rankin約化算法的局部分析100-105
• B.1 幺模變換矩陣的尺度100-102
• B.2 Algorithm 21和Algorithm 22的分析102-105
• 致謝105-107
• 個人簡歷、在學期間發(fā)表的學術論文與研究成果107

【相似文獻】

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 李建偉;格理論中計算格基和格基約化問題研究[D];清華大學;2015年

  本文關鍵詞：格理論中計算格基和格基約化問題研究，，由筆耕文化傳播整理發(fā)布。

本文編號：357021