10
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Algorithms on Ideal over Complex Multiplication order

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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.

          Related collections

          Author and article information

          Journal
          2016-02-29
          Article
          1602.09037
          5214dc00-a3b2-44f0-b78a-efe147a0f36b

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          Full version of a paper submitted to ANTS
          cs.DS cs.CR cs.DM math.NT

          Data structures & Algorithms,Security & Cryptology,Discrete mathematics & Graph theory,Number theory

          Comments

          Comment on this article