Lattices with Symmetry

被引：11

作者：

Lenstra, H. W., Jr. ^{[1
]}

Silverberg, A. ^{[2
]}

机构：

[1] Leiden Univ, Mathematisch Inst, Leiden, Netherlands

[2] Univ Calif Irvine, Dept Math, Irvine, CA 92697 USA

来源：

JOURNAL OF CRYPTOLOGY | 2017年 / 30卷 / 03期

关键词：

Lattices; Gentry-Szydlo algorithm; Ideal lattices; Lattice-based cryptography;

D O I：

10.1007/s00145-016-9235-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

For large ranks, there is no good algorithm that decides whether a given lattice has an orthonormal basis. But when the lattice is given with enough symmetry, we can construct a provably deterministic polynomial-time algorithm to accomplish this, based on the work of Gentry and Szydlo. The techniques involve algorithmic algebraic number theory, analytic number theory, commutative algebra, and lattice basis reduction.

引用

页码：760 / 804

页数：45

共 11 条

[1] Atiyah M. F., 1969, Introduction to Commutative Algebra
[2] Bourbaki N., 2007, Elements de mathematique
[3] Bourbaki N., 1998, Elements of Mathematics
[4] Gentry C, 2002, LECT NOTES COMPUT SC, V2332, P299
[5] HEATHBROWN DR, 1992, P LOND MATH SOC, V64, P265
[6] Lang S., 2012, ALGEBRA, V211
[7] FACTORING POLYNOMIALS WITH RATIONAL COEFFICIENTS
LENSTRA, AK
LENSTRA, HW
LOVASZ, L
[J]. MATHEMATISCHE ANNALEN, 1982, 261 (04) : 515 - 534
[8] Lenstra HW, 2014, LECT NOTES COMPUT SC, V8616, P280, DOI 10.1007/978-3-662-44371-2_16
[9] Roots of Unity in Orders
Lenstra, H. W., Jr.
Silverberg, A.
[J]. FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2017, 17 (03) : 851 - 877
[10] Determining cyclicity of finite modules
Lenstra, H. W., Jr.
Silverberg, A.
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 2016, 73 : 153 - 156

← 1 2 →