Algorithms for ray class groups and Hilbert class fields

the Twenty-First Annual ACM(Association for Cpmputing Machinery)-SIAM(Society for Industrial and Applied Mathematics) Symposium on Discrete Algorithms

Kirsten Eisenträger ; Sean Hallgren

Others  :  http://www.siam.org/proceedings/soda/2010/SODA10_040_eisentragerk.pdf
PID  :  18238

来源: CEUR

【 摘 要 】

This paper analyzes the complexity of problems from class field theory. Class field theory can be used to show the existence of infinite families of number fields with constant root discriminant. Such families have been proposed for use in lattice-based cryptography and for constructing error-correcting codes. Little is known about the complexity of computing them. We show that computing the ray class group and computing certain subfields of Hilbert class fields efficiently reduce to known computationally difficult problems. These include computing the unit group and class group, the principal ideal problem, factoring, and discrete log. As a consequence, efficient quantum algorithms for these problems exist in constant degree number fields.