CaltechAUTHORS
Published May 2002 | Version public
Book Section - Chapter Metadata-only

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

Creators

  • 1. ROR icon California Institute of Technology

Contributors

Other:

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.

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.

Additional details

Identifiers

Eprint ID
71680
DOI
10.1145/509907.510001
Resolver ID
CaltechAUTHORS:20161102-140613462

Related works

Describes
10.1145/509907.510001 (DOI)

Funding

NSF
CCF-0049092
Charles Lee Powell Foundation
Air Force Office of Scientific Research (AFOSR)
F30602-01-2-0524
NSF
CISE-9876172
Defense Advanced Research Projects Agency (DARPA)

Dates

Created
2016-11-02
Created from EPrint's datestamp field
Updated
2021-11-11
Created from EPrint's last_modified field