Testing Isomorphism of Lattices over CM-Orders
Testing Isomorphism of Lattices over CM-Orders
复制标题
测试 CM 阶晶格的同构
DOI：
10.1137/17m115390x
复制
发表时间：
2019
影响因子：
1.6
通讯作者：
Silverberg, Alice
中科院分区：
文献类型：
--
作者：
Lenstra, Hendrik W.;Silverberg, Alice
acm -序是一个简化的顺序配备了一个对合，模仿复杂的共轭。这一阶的witt—Picard群是与类群的“负部分”密切相关的某一理想类群。我们提出了一个确定性多项式时间算法来解决以下问题，这可以看作是主要理想检验问题的一个特例：给定一个cm阶，确定其Witt—Picard群中的两个给定元素是否相等。为了防止系数爆破，该算法使用格而不是理想来操作。一个重要的组成部分是Gentry和Szydlo在密码学上下文中引入的一种技术。我们将它应用到cm阶格上，取决于从初等数论中的Konyagin和Pomerance的结果中推导出的辅助理想的一个新的存在性定理。
ACM-orderis a reduced order equipped with an involution that mimics complex conjugation. TheWitt--Picard groupof such an order is a certain group of ideal classes that is closely related to the “minus part” of the class group. We present a deterministic polynomial-time algorithm for the following problem, which may be viewed as a special case of the principal ideal testing problem: given a CM-order, decide whether two given elements of its Witt--Picard group are equal. In order to prevent coefficient blow-up, the algorithm operates with lattices rather than with ideals. An important ingredient is a technique introduced by Gentry and Szydlo in a cryptographic context. Our application of it to lattices over CM-orders hinges upon a novel existence theorem for auxiliary ideals, which we deduce from a result of Konyagin and Pomerance in elementary number theory.