Hallgren, Sean (2002) Polynomial-Time Quantum Algorithms for Pell’s Equation and the Principal Ideal Problem. In: STOC '02 Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM , New York, Ny, pp. 653-658. ISBN 1-58113-495-9. https://resolver.caltech.edu/CaltechAUTHORS:20161102-140613462
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161102-140613462
Abstract
We give polynomial-time quantum algorithms for two problems from computational algebraic number theory. The first is Pell’s equation. Given a positive non-square integer d, Pell’s equation is x^2 − dy^2 = 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 the principal 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.
| Item Type: | Book Section | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||||||||
| Additional Information: | © 2002 ACM. Supported in part by an NSF Mathematical Scienes Postdoctoral Fellowship, NSF through Caltech’s Institute for Quantum Information, NSF under grant no. 0049092 (previously 9876172) and The Charles Lee Powell Foundation. Part of this work done while the author was at MSRI and U.C. Berkeley, with partial support from DARPA QUIST Agreement No. F30602-01-2-0524. | ||||||||||||
| Funders: |
| ||||||||||||
| Subject Keywords: | Theory | ||||||||||||
| Classification Code: | F.2. 1[ Analysis Of Algorithms And Problem Complexity ]: Numerical Algorithms and Problems | ||||||||||||
| DOI: | 10.1145/509907.510001 | ||||||||||||
| Record Number: | CaltechAUTHORS:20161102-140613462 | ||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20161102-140613462 | ||||||||||||
| Official Citation: | Sean Hallgren. 2002. Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (STOC '02). ACM, New York, NY, USA, 653-658. DOI: http://dx.doi.org/10.1145/509907.510001 | ||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
| ID Code: | 71680 | ||||||||||||
| Collection: | CaltechAUTHORS | ||||||||||||
| Deposited By: | Kristin Buxton | ||||||||||||
| Deposited On: | 02 Nov 2016 23:35 | ||||||||||||
| Last Modified: | 11 Nov 2021 04:49 |
Repository Staff Only: item control page
