Jean-Francois Biasse: A polynomial time quantum algorithm for computing class groups

Опубликовано 3 февраля 2017, 19:39

"This paper presents a polynomial time quantum algorithms for computing the
ideal class group and solving the principal ideal problem (PIP) in
arbitrary classes of number fields under the Generalized Riemann
Hypothesis. Previously, these problems were known to have polynomial time
solutions in classes of fixed degree number fields by a result of Hallgren
[Hallgren'STOC05]. Our new algorithm relies on the recent quantum polynomial time algorithm for solving the Hidden Subgroup Problem of Eistentrager et al. [EHKS STOC14].

Computing the class group and solving the PIP are fundamental problems in
number theory. In particular, they are connected to many unproven
conjectures in both analytic and algebraic number theory. Our algorithms
also directly apply to the computation of relative class groups and unit
groups, to the computation of ray class groups and to the the resolution
of norm equations. Moreover, the resolution of the PIP is a key component
in the cryptanalysis of cryptosystems based on the hardness of finding a
short generator in a principal ideal."