Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of the ACM

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

Sean Hallgren

Published Mar 1, 2007• 151 citations
Publisher

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

DOI
10.1145/1206035.1206039

Related papers

Fast quantum algorithms for computing the unit group and class group of a number field

Sean Hallgren

Computing the unit group and class group of a number field are two of the main tasks in computational algebraic number theory. Factoring integers reduces to solving Pell's equation, which is a special case of computing the unit group, but a reduction in the other direction is not known and appears more difficult. We give polynomial-time quantum algorithms for computing the unit group and class group when the number field has constant degree.

ACM Symposium on Theory of Computing (STOC)•May 22, 2005•83 citations

Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields

Jean‐François Biasse, Fang Song

This paper gives polynomial time quantum algorithms for computing the ideal class group (CGP) under the Generalized Riemann Hypothesis and solving the principal ideal problem (PIP) in number fields of arbitrary degree. These are are fundamental problems in number theory and they are connected to many unproven conjectures in both analytic and algebraic number theory. Previously the best known algorithms by Hallgren [20] only allowed to solve these problems in quantum polynomial time for number fields of constant degree. In a recent breakthrough, Eisenträger et al. [11] showed how to compute the unit group in arbitrary fields, thus opening the way to the resolution of CGP and PIP in the general case. For example, Biasse and Song [3] pointed out how to directly apply this result to solve PIP in classes of cyclotomic fields of arbitrary degree. The methods we introduce in this paper run in quantum polynomial time in arbitrary classes of number fields. They can be applied to solve other problems in computational number theory as well including computing the ray class group and solving relative norm equations. They are also useful for ongoing cryptanalysis of cryptographic schemes based on ideal lattices [5, 10]. Our algorithms generalize the quantum algorithm for computing the (ordinary) unit group [11]. We first show that CGP and PIP reduce naturally to the computation of S-unit groups, which is another fundamental problem in number theory. Then we show an efficient quantum reduction from computing S-units to the continuous hidden subgroup problem introduced in [11]. This step is our main technical contribution, which involves careful analysis of the metrical properties of lattices to prove the correctness of the reduction. In addition, we show how to convert the output into an exact compact representation, which is convenient for further algebraic manipulations.

ACM-SIAM Symposium on Discrete Algorithms (SODA)•Dec 21, 2015•111 citations

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

Sean Hallgren

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

ACM Symposium on Theory of Computing (STOC)•May 19, 2002•162 citations

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

Sean Hallgren

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

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2002•28 citations

Notes on Hallgren's efficient quantum algorithm for solving Pell's equation

Richard Jozsa

Pell's equation is x^2-d*y^2=1 where d is a square-free integer and we seek positive integer solutions x,y>0. Let (x',y') be the smallest solution (i.e. having smallest A=x'+y'sqrt(d)). Lagrange showed that every solution can easily be constructed from A so given d it suffices to compute A. It is known that A can be exponentially large in d so just to write down A we need exponential time in the input size log d. Hence we introduce the regulator R=ln A and ask for the value of R to n decimal places. The best known classical algorithm has sub-exponential running time O(exp(sqrt(log d)), poly(n)). Hallgren's quantum algorithm gives the result in polynomial time O(poly(log d),poly(n)) with probability 1/poly(log d). The idea of the algorithm falls into two parts: using the formalism of algebraic number theory we convert the problem of solving Pell's equation into the problem of determining R as the period of a function on the real numbers. Then we generalise the quantum Fourier transform period finding algorithm to work in this situation of an irrational period on the (not finitely generated) abelian group of real numbers. These notes are intended to be accessible to a reader having no prior acquaintance with algebraic number theory; we give a self contained account of all the necessary concepts and we give elementary proofs of all the results needed. Then we go on to describe Hallgren's generalisation of the quantum period finding algorithm, which provides the efficient computational solution of Pell's equation in the above sense.

arXiv:quant-ph/0302134•Feb 18, 2003•21 citations

Quantum algorithms for one-dimensional infrastructures

Pradeep Kiran Sarvepalli, Paweł Wocjan

Infrastructures are group-like objects that make their appearance in arithmetic geometry in the study of computational problems related to number fields and function fields over finite fields. The most prominent computational tasks of infrastructures are the computation of the circumference of the infrastructure and the generalized discrete logarithms. Both these problems are not known to have efficient classical algorithms for an arbitrary infrastructure. Our main contributions are polynomial time quantum algorithms for one-dimensional infrastructures that satisfy certain conditions. For instance, these conditions are always fulfilled for infrastructures obtained from number fields and function fields, both of unit rank one. Since quadratic number fields give rise to such infrastructures, this algorithm can be used to solve Pell's equation and the principal ideal problem. In this sense we generalize Hallgren's quantum algorithms for quadratic number fields, while also providing a polynomial speedup over them. Our more general approach shows that these quantum algorithms can also be applied to infrastructures obtained from complex cubic and totally complex quartic number fields. Our improved way of analyzing the performance makes it possible to show that these algorithms succeed with constant probability independent of the problem size. In contrast, the lower bound on the success probability due to Hallgren decreases as the fourth power of the logarithm of the circumference. Our analysis also shows that fewer qubits are required. We also contribute to the study of infrastructures, and show how to compute efficiently within infrastructures.

arXiv:1106.6347•Quantum Information and Computation•Jan 1, 2014•6 citations
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 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.
This paper gives polynomial time quantum algorithms for computing the ideal class group (CGP) under the Generalized Riemann Hypothesis and solving the principal ideal problem (PIP) in number fields of arbitrary degree. These are are fundamental problems in number theory and they are connected to many unproven conjectures in both analytic and algebraic number theory. Previously the best known algorithms by Hallgren [20] only allowed to solve these problems in quantum polynomial time for number fields of constant degree. In a recent breakthrough, Eisenträger et al. [11] showed how to compute the unit group in arbitrary fields, thus opening the way to the resolution of CGP and PIP in the general case. For example, Biasse and Song [3] pointed out how to directly apply this result to solve PIP in classes of cyclotomic fields of arbitrary degree. The methods we introduce in this paper run in quantum polynomial time in arbitrary classes of number fields. They can be applied to solve other problems in computational number theory as well including computing the ray class group and solving relative norm equations. They are also useful for ongoing cryptanalysis of cryptographic schemes based on ideal lattices [5, 10]. Our algorithms generalize the quantum algorithm for computing the (ordinary) unit group [11]. We first show that CGP and PIP reduce naturally to the computation of S-unit groups, which is another fundamental problem in number theory. Then we show an efficient quantum reduction from computing S-units to the continuous hidden subgroup problem introduced in [11]. This step is our main technical contribution, which involves careful analysis of the metrical properties of lattices to prove the correctness of the reduction. In addition, we show how to convert the output into an exact compact representation, which is convenient for further algebraic manipulations.
Pell's equation is x^2-d*y^2=1 where d is a square-free integer and we seek positive integer solutions x,y>0. Let (x',y') be the smallest solution (i.e. having smallest A=x'+y'sqrt(d)). Lagrange showed that every solution can easily be constructed from A so given d it suffices to compute A. It is known that A can be exponentially large in d so just to write down A we need exponential time in the input size log d. Hence we introduce the regulator R=ln A and ask for the value of R to n decimal places. The best known classical algorithm has sub-exponential running time O(exp(sqrt(log d)), poly(n)). Hallgren's quantum algorithm gives the result in polynomial time O(poly(log d),poly(n)) with probability 1/poly(log d). The idea of the algorithm falls into two parts: using the formalism of algebraic number theory we convert the problem of solving Pell's equation into the problem of determining R as the period of a function on the real numbers. Then we generalise the quantum Fourier transform period finding algorithm to work in this situation of an irrational period on the (not finitely generated) abelian group of real numbers. These notes are intended to be accessible to a reader having no prior acquaintance with algebraic number theory; we give a self contained account of all the necessary concepts and we give elementary proofs of all the results needed. Then we go on to describe Hallgren's generalisation of the quantum period finding algorithm, which provides the efficient computational solution of Pell's equation in the above sense.
Infrastructures are group-like objects that make their appearance in arithmetic geometry in the study of computational problems related to number fields and function fields over finite fields. The most prominent computational tasks of infrastructures are the computation of the circumference of the infrastructure and the generalized discrete logarithms. Both these problems are not known to have efficient classical algorithms for an arbitrary infrastructure. Our main contributions are polynomial time quantum algorithms for one-dimensional infrastructures that satisfy certain conditions. For instance, these conditions are always fulfilled for infrastructures obtained from number fields and function fields, both of unit rank one. Since quadratic number fields give rise to such infrastructures, this algorithm can be used to solve Pell's equation and the principal ideal problem. In this sense we generalize Hallgren's quantum algorithms for quadratic number fields, while also providing a polynomial speedup over them. Our more general approach shows that these quantum algorithms can also be applied to infrastructures obtained from complex cubic and totally complex quartic number fields. Our improved way of analyzing the performance makes it possible to show that these algorithms succeed with constant probability independent of the problem size. In contrast, the lower bound on the success probability due to Hallgren decreases as the fourth power of the logarithm of the circumference. Our analysis also shows that fewer qubits are required. We also contribute to the study of infrastructures, and show how to compute efficiently within infrastructures.