格理论中计算格基和格基约化问题研究

发布时间：2017-05-11 10:07

  本文关键词：格理论中计算格基和格基约化问题研究，由笔耕文化传播整理发布。

【摘要】：这篇论文旨在研究格理论中两个非常基础又非常重要的计算问题:计算格基问题和格基约化问题.计算格基问题指的是给定一组格生成元,计算它们生成的格的一组基.格基约化问题则是给定一组格基,计算出具有某种较好性质的格基,或者是向量长度较短,或者是局部向量张成的体积较小等.这两个计算问题关系密切,互为交叉:计算格基是进行格基约化的前提;格基约化过程的局部处理常常涉及计算格基,而且格基约化方法经过适当的修正也能用来计算格基.两者作为基本问题有着重要和广泛的应用.例如,计算格基算法可以用来确定代数数域中的基本单位元,格基约化算法是密码分析的重要工具.因此,研究这两个问题的理论价值和实际意义不言而喻.本文的第一项工作是较为系统地研究了计算格基算法.先前的计算格基算法中,具有线性输出基的算法不具有拟线性时间复杂性,而具有拟线性时间复杂性的算法不具有线性输出基.我们通过引入Euclid交换、正则系统、松弛约化和按块交换等新的技术和想法,首次给出了一个同时具有线性输出基和时间复杂性关于log‖B0‖拟线性的计算格基算法,并且在标准算术下复杂性是O(mn4(log n+log‖B0‖)2),其中B0∈Zm×n表示输入的格生成元.我们进而给出了具有线性输出基和拟线性时间复杂性的本原向量组格基扩充算法.本文的第二项工作是探讨了滑动约化基的性质.作为当前理论上最好的近似求解最短向量问题的格基约化算法,Gama-Nguyen滑动约化算法被视为著名的Mordell不等式的算法实现.通过推广先前的证明方法,我们推导了Gama-Nguyen滑动约化基与逐次极小值之间的比例关系,从而对该类型基的约化程度给出了更全面的刻划.本文的第三项工作是给出了一个近似求解最小体积问题的格基约化算法.我们证明了一个新的关于Rankin常数的不等式,该不等式用低维Rankin常数γk,r给出高维Rankin常数γn,r的上界.通过推广先前的约化概念,我们给出了输出因子对应上述新Rankin不等式的一个格基约化算法.该算法能确定性地在多项式时间内近似求解最小体积问题.这一项工作可以看成是经典的Mordell不等式和Gama-Nguyen滑动约化算法的延续.
【关键词】：计算格基 格基约化 最短向量问题 最小体积问题 拟线性算法
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O153.1
【目录】：

• 摘要3-4
• Abstract4-8
• 主要符号对照表8-9
• 第1章 绪论9-20
• 1.1 选题背景和意义9-11
• 1.2 国内外研究现状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常数和Rankin常数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框架的优化算法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不等式的经典证明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常数的新不等式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
• 个人简历、在学期间发表的学术论文与研究成果107

【相似文献】

中国博士学位论文全文数据库 前1条

1 李建伟;格理论中计算格基和格基约化问题研究[D];清华大学;2015年

  本文关键词：格理论中计算格基和格基约化问题研究，，由笔耕文化传播整理发布。

本文编号：357021