Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem

Sean Hallgren

doi:10.1145/509998.510001

Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem

Sean Hallgren

Computer Science and Engineering

Research output: Contribution to journal › Conference article › peer-review

90 Scopus citations

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² - dy² = 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.

Original language	English (US)
Pages (from-to)	653-658
Number of pages	6
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/509998.510001
State	Published - 2002
Event	Proceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada Duration: May 19 2002 → May 21 2002

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/509998.510001

Cite this

@article{c0c657031e79487a9cce0860c239ac47,

title = "Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem",

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 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 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.",

author = "Sean Hallgren",

year = "2002",

doi = "10.1145/509998.510001",

language = "English (US)",

pages = "653--658",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 34th Annual ACM Symposium on Theory of Computing ; Conference date: 19-05-2002 Through 21-05-2002",

}

TY - JOUR

T1 - Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem

AU - Hallgren, Sean

PY - 2002

Y1 - 2002

N2 - 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 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 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.

AB - 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 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 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.

UR - http://www.scopus.com/inward/record.url?scp=0036038402&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036038402&partnerID=8YFLogxK

U2 - 10.1145/509998.510001

DO - 10.1145/509998.510001

M3 - Conference article

AN - SCOPUS:0036038402

SN - 0734-9025

SP - 653

EP - 658

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 34th Annual ACM Symposium on Theory of Computing

Y2 - 19 May 2002 through 21 May 2002

ER -

Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this