Testing isomorphism of lattices over CM-orders
Skip to main content
eScholarship
Open Access Publications from the University of California

Testing isomorphism of lattices over CM-orders

  • Author(s): Jr, HWL
  • Silverberg, A
  • et al.
Creative Commons Attribution 4.0 International Public License
Abstract

A CM-order is a reduced order equipped with an involution that mimics complex conjugation. The Witt-Picard group of 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.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View