Fast quantum algorithms for computing the unit group and class group of a number field
Author:
Open Access
- 22 May 2005
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 468-474
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.Keywords
This publication has 8 references indexed in Scilit:
- Polynomial time quantum algorithm for the computation of the unit group of a number field2005
- Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem2002
- Complexity of Lattice Problems2002
- Quantum Fourier sampling simplified1999
- On the Power of Quantum ComputationSIAM Journal on Computing, 1997
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- Under the assumption of the Generalized Riemann Hypothesis verifying the class number belongs to NP ∩ co-NPLecture Notes in Computer Science, 1994
- A Course in Computational Algebraic Number Theory1993