Paper 2016/220

Algorithms on Ideal over Complex Multiplication order

Paul Kirchner

Abstract

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- Silverberg’s 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.

Note: One mistake was removed.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
paul kirchner @ ens fr
History
2016-04-06: revised
2016-02-29: received
See all versions
Short URL
https://ia.cr/2016/220
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/220,
      author = {Paul Kirchner},
      title = {Algorithms on Ideal over Complex Multiplication order},
      howpublished = {Cryptology ePrint Archive, Paper 2016/220},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/220}},
      url = {https://eprint.iacr.org/2016/220}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.