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

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

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

【相似文獻(xiàn)】

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

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

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

本文編號(hào)：357021