Lattices with Symmetry
Lattices with Symmetry
复制标题
具有对称性的格子
作者：
H. Lenstra;A. Silverberg
对于大的秩，没有好的算法来决定给定的格是否有正交基。但是当格具有足够的对称性时，我们可以基于Gentry和Szydlo的工作构造一个可证明确定的多项式时间算法来实现这一点。这些技术涉及算法代数数论，解析数论，交换代数和格基约简。
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.