Hallgren, Sean
(2007)
*Polynomial-Time Quantum Algorithms for Pell’s Equation
and the Principal Ideal Problem.*
Journal of the ACM, 54
(1).
pp. 653-658.
ISSN 0004-5411.
https://resolver.caltech.edu/CaltechAUTHORS:20111101-105856791

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:20111101-105856791

## 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: | Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| ||||||||||||

Additional Information: | © 2002 ACM, Inc. 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. Thanks to Hendrik Lenstra for many useful discussions and for suggesting these problems. Also thanks to Kirsten Eisenträger, Ashwin Nayak, Umesh Vazirani, and Ulrich Vollmer for useful discussions. | ||||||||||||

Funders: |
| ||||||||||||

Subject Keywords: | Theory | ||||||||||||

Issue or Number: | 1 | ||||||||||||

Record Number: | CaltechAUTHORS:20111101-105856791 | ||||||||||||

Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20111101-105856791 | ||||||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||

ID Code: | 27552 | ||||||||||||

Collection: | CaltechAUTHORS | ||||||||||||

Deposited By: | Jason Perez | ||||||||||||

Deposited On: | 01 Nov 2011 23:13 | ||||||||||||

Last Modified: | 03 Oct 2019 03:24 |

Repository Staff Only: item control page