2017/06/22 by Lenstra, Hendrik W., Silverberg, Alice
#11Y16 (primary) #68W30 (secondary) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1706.07373
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.