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• 147 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•79 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•99 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•8 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•156 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•22 citations

An efficient quantum algorithm for computing $S$-units and its applications

Jean‐François Biasse, Song, Fang

In this paper, we provide details on the proofs of the quantum polynomial time algorithm of Biasse and Song (SODA 16) for computing the $S$-unit group of a number field. This algorithm directly implies polynomial time methods to calculate class groups, S-class groups, relative class group and the unit group, ray class groups, solve the principal ideal problem, solve certain norm equations, and decompose ideal classes in the ideal class group. Additionally, combined with a result of Cramer, Ducas, Peikert and Regev (Eurocrypt 2016), the resolution of the principal ideal problem allows one to find short generators of a principal ideal. Likewise, methods due to Cramer, Ducas and Wesolowski (Eurocrypt 2017) use the resolution of the principal ideal problem and the decomposition of ideal classes to find so-called ``mildly short vectors'' in ideal lattices of cyclotomic fields.

arXiv:2510.02280•Oct 2, 2025•0 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.
An efficient quantum algorithm for computing SSS-units and its applications
In this paper, we provide details on the proofs of the quantum polynomial time algorithm of Biasse and Song (SODA 16) for computing the SSS-unit group of a number field. This algorithm directly implies polynomial time methods to calculate class groups, S-class groups, relative class group and the unit group, ray class groups, solve the principal ideal problem, solve certain norm equations, and decompose ideal classes in the ideal class group. Additionally, combined with a result of Cramer, Ducas, Peikert and Regev (Eurocrypt 2016), the resolution of the principal ideal problem allows one to find short generators of a principal ideal. Likewise, methods due to Cramer, Ducas and Wesolowski (Eurocrypt 2017) use the resolution of the principal ideal problem and the decomposition of ideal classes to find so-called ``mildly short vectors'' in ideal lattices of cyclotomic fields.