Title: Testing isomorphism of lattices over CM-orders,
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.