IACR News item: 29 February 2016
Paul Kirchner
ePrint Report
We show in this paper that the Gentry-Szydlo algorithm for cyclotomic orders, previously
revisited by Lenstra-Silverberg, can be extended to complex-multiplication (CM) orders, and
even to a more general structure. This algorithm allows to test equality over the polarized ideal
class group, and finds a generator of the polarized ideal in polynomial time. Also, the algorithm
allows to solve the norm equation over CM orders and the recent reduction of principal ideals to
the real suborder can also be performed in polynomial time. Furthermore, we can also compute in
polynomial time a unit of an order of any number field given a (not very precise) approximation
of it.
Our description of the Gentry-Szydlo algorithm is different from the original and Lenstra-
Silverbergs variant and we hope the simplifications made will allow a deeper understanding.
Finally, we show that the well-known speed-up for enumeration and sieve algorithms for ideal
lattices over power of two cyclotomics can be generalized to any number field with many roots
of unity.
Additional news items may be found on the IACR news page.