Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
Top Cited Papers
- 1 March 2007
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 54 (1) , 1-19
- https://doi.org/10.1145/1206035.1206039
Abstract
Besides Shor's polynomial-time quantum algorithms for factoring and discrete log, all progress in understanding when quantum algorithms have an exponential advantage over classical algo- rithms has been through oracle problems. Here we give efficient quantum algorithms for two more non-oracle problems. The first is Pell's equation. Given a positive non-square integer d, Pell's equation is x2 − dy2 = 1 and the goal is to find its integer solutions. Factoring integers reduces to finding integer solutions of Pell's equation, but a reduction in the other direction is not known and appears more difficult. The second problem is theprincipal ideal problem in real quadratic number fields. Solving this problem is at least as hard as solving Pell's equation, and is the basis of a cryptosystem which is broken by our algorithm. We also state some related open problems from the area of computational algebraic number theory.Keywords
This publication has 11 references indexed in Scilit:
- Hidden translation and orbit coset in quantum computingPublished by Association for Computing Machinery (ACM) ,2003
- Why haven't more quantum algorithms been found?Journal of the ACM, 2003
- Quantum algorithms for solvable groupsPublished by Association for Computing Machinery (ACM) ,2001
- Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problemPublished by Association for Computing Machinery (ACM) ,2001
- Normal subgroup reconstruction and quantum computation using group representationsPublished by Association for Computing Machinery (ACM) ,2000
- Quantum Complexity TheorySIAM Journal on Computing, 1997
- 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
- Short Representation of Quadratic IntegersPublished by Springer Nature ,1995
- Some remarks concerning the complexity of computing class groups of quadratic fieldsJournal of Complexity, 1991