Fast quantum algorithms for computing the unit group and class group of a number field

ABSTRACT

Computing the unit group and class group of a number field are two of the main tasks in computational algebraic number theory. Factoring integers reduces to solving Pell's equation, which is a special case of computing the unit group, but a reduction in the other direction is not known and appears more difficult. We give polynomial-time quantum algorithms for computing the unit group and class group when the number field has constant degree.

REFERENCES

• 1: Johannes Buchmann , Michael Pohst, Computing a lattice basis from a system of generating vectors, Proceedings of the European Conference on Computer Algebra, p.54-63, June 02-05, 1987
• 2: J. Buchmann and H. C. Williams. On the existence of a short proof for the value of the class number and regulator of a real quadratic field. In Number theory and applications (Banff, AB, 1988), pages 327--345. Kluwer Acad. Publ., Dordrecht, 1989.
• 3: Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 4: Lisa Hales , Sean Hallgren, Quantum Fourier sampling simplified, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.330-338, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301336]
• 5: Sean Hallgren, Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510001]
• 6: H. W. Lenstra, Jr. Algorithms in algebraic number theory. Bulliten of the American Mathematical Society, 26(2):221--244, Apr. 1992.
• 7: Daniele Micciancio , S. Goldwasser, Complexity of Lattice Problems, Kluwer Academic Publishers, Norwell, MA, 2002
• 8: Arthur Schmidt , Ulrich Vollmer, Polynomial time quantum algorithm for the computation of the unit group of a number field, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060661]
• 9: R. Schoof. Computing Arakelov class groups. To appear, 2004.
• 10: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 11: Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]
• 12: Christoph Thiel, Under the assumption of the generalized Riemann Hyothesis verifying the class number belongs to NPcapCo-NP, Proceedings of the First International Symposium on Algorithmic Number Theory, p.234-247, May 06-09, 1994
• 13: C. Thiel. On the complexity of some problems in algorithmic algebraic number theory. PhD thesis, Universität des Saarlandes, Saarbrücken, Germany, 1995.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
class group, computational algebraic number theory, quantum algorithms, unit group