Testing isomorphism of lattices over CM-orders
This work addresses a computational problem in algebraic number theory, with potential applications in cryptography, but it is incremental as it builds on existing techniques.
The paper tackles the problem of testing isomorphism of lattices over CM-orders, presenting a deterministic polynomial-time algorithm to decide equality of elements in the Witt-Picard group, which is a special case of principal ideal testing.
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.