CaltechAUTHORS
  A Caltech Library Service

Polynomial-Time Quantum Algorithms for Pell’s Equation and the Principal Ideal Problem

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:
URLURL TypeDescription
http://dx.doi.org/10.1145/509907.510001DOIArticle
http://dl.acm.org/citation.cfm?doid=509907.510001PublisherArticle
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:
Funding AgencyGrant Number
NSFCCF-0049092
Charles Lee Powell FoundationUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)F30602-01-2-0524
NSFCISE-9876172
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Subject Keywords:Theory
Classification Code:F.2. 1[ Analysis Of Algorithms And Problem Complexity ]: Numerical Algorithms and Problems
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:03 Oct 2019 16:10

Repository Staff Only: item control page