期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

原-对偶规约基与连续最小元 被引量：1

Primal-Dual Bases and Successive Minima
下载PDF
导出
摘要 最近Koy提出一种质量优于LLL规约基的原-对偶规约基,但没有给出该规约基与最小元比值因子的上界和下界.本文首先分析了原-对偶规约基的性质,然后给出并证明了原-对偶规约基与连续最小元比值因子的上界和下界,最后用原-对偶规约基改进Babai的近似CVP算法——舍入算法,提高了其近似因子. Recently Koy proposed primal-dual bases which have better quality than LLL-reduced bases in high-dimensional lattice,but his efforts did not take into account the low and upper bounds for the ratios of primal-dual bases to successive minima. In this paper some useful properties of Koy＇ s primal-dual bases are analyzed and then the low and upper bounds for the ratios of primal-dual bases to successive minima are introduced and proved.At the end, the Round-off algorithm for the approximate-CVP is improved using primal-dual bases and its result has a better approximation factor than L. Babai＇ s.
作者 谢朝海 陶然 王越 李继勇
机构地区 北京理工大学信息科学技术学院
出处 《电子学报》 EI CAS CSCD 北大核心 2008年第6期1124-1129,共6页 Acta Electronica Sinica
基金 国家863高技术研究发展计划(No.2006AA01Z450) 国防基础科研项目(No.C1120060497)
关键词 格 规约基 连续最小元 长度亏损 最近向量问题 lattice reduced bases successive minima length defect the closest vector problem（CVP）
分类号 TP393 [自动化与计算机技术—计算机应用技术] O15 [理学—基础数学]
  • 相关文献

参考文献14

  • 1P Nguyen, J Stem. Lattice reduction in cryptology: An update [A ]. W. Bosma. Algorithmic Number Theory-Proceedings of ANTS-IV, Lecture Notes in Computer Science, vol. 1838 [ C ]. Berlin: Springer-Verlag, 2000.85 - 112.
  • 2C P Schnorr. A hierarchy of polynomial lattice basis reduction algorithms[ J]. Theoretical Computer Science, 1987,53(2) : 201 - 224.
  • 3H Koy. Primal/duale Segment-Reduktion von Gitterbasen[ EB/ OL]. http://www. mi. informatik. unifmnkfurt. de/research/ papers. html.
  • 4C P Schnorr. Blockwise Lattice Basis Reduction Revisited[ EB/ OL]. http://www. mi. informatik, uni-franlffurt. de/research/ papers. html.
  • 5C P Schnorr. Fast LLL-type lattice reduction[J] . Information and Computation, 2006,204( 1 ) : 1 - 25.
  • 6K Mahler. A theorem on inhomogeneous diophantine inequalities[ J ]. Nederl Akad Wetensch, Proc, 1938,4: 634 - 637.
  • 7J C Lagarias, H W Lenstra, C P Schnorr. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal latdce[ J]. Combinatorica, 1990,10(4) :333 - 348.
  • 8A K Lenstra, H W Lenstra, L Lovasz. Factoring polynomials with rational coefficients[ J] .Math Ann, 1982,261:515 - 534.
  • 9C P Schnorr. Block reduced lattice bases and successive minima[ J]. Combinatorics, Probability and Computing, 1994, (3) :507 - 533.
  • 10L Babai. On Lovasz lattice reduction and the nearest lattice point brobleml J]. Combinatorica, 1986,6( 1 ) : 1 - 13.

同被引文献18

  • 1Nguyen P Q. SternJ. Lattice reduction in cryptolo?gy: an update[CJ/ /Hanrot G. Morain F. Thome E. Algorithmic Number Theory. Berlin: Springer. 2000: 85.
  • 2Gama N. How-Grave-Graham N. Koy H. et al. Rankin's constant and blockwise lattice reduction[CJ/ /Cynthia D. Advances in Cryptology-CRYPTO 2006. Berlin: Springer. 2006: 112.
  • 3Nguyen P Q. Regen O. Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures[J].Journal of Cryptology. 2009. 22(2): 139.
  • 4Schnorr C P. A hierarchy of polynomial lattice basis reduction algorithms[J]. Theoretical Computer Sci?ence. 1987. 53: 20l.
  • 5Koy H. Schnorr C P. Segment LLL-reduction of lat?tice bases[CJ/ /Silverman] H. Cryptography and Lattices. Berlin: Springer. 2001: 67.
  • 6Koy H. Schnorr C P. Segment LLL-reduction with floating point orthogonalization[CJ/ /Silverman] H. Cryptography and Lattices. Berlin: Springer, 2001: 81.
  • 7Nguyen. The LLL algorithmj M]. Berlin: Spring?er. 2010: 169.
  • 8Mehrotra S, Li Z. Segment LLL reduction of lattice bases using modular arithmetic[J]. Algorithms. 2010, 3(3): 224.
  • 9Lovdsz L. Scarf H. The generalized basis reduction algorithm[J]. Mathematics of Operations Research, 1992, 17 (3): 754.
  • 10Cook W, Rutherpord T, Scarf H E, et al. An im?plementation of the generalized basis reduction algo?rithm for integer programmingj'J].Journal on Com?puting, 1993, 5(2): 208.

引证文献1

二级引证文献1

电子学报
2008年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部