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

Access Restriction
Subscribed

 Author Hallgren, Sean Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2007 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Quantum algorithms ♦ Quantum computation Abstract We give polynomial-time quantum algorithms for three problems from computational algebraic number theory. The first is Pell's equation. Given a positive nonsquare integer $\textit{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 we solve is the principal ideal problem in real quadratic number fields. This problem, which is at least as hard as solving Pell's equation, is the one-way function underlying the Buchmann--Williams key exchange system, which is therefore broken by our quantum algorithm. Finally, assuming the generalized Riemann hypothesis, this algorithm can be used to compute the class group of a real quadratic number field. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2007-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 54 Issue Number 1 Page Count 19 Starting Page 1 Ending Page 19

#### Open content in new tab

Source: ACM Digital Library