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.
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.
An efficient quantum algorithm for computing S-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 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.
Computing the group of units in a field of algebraic numbers is one of the central tasks of computational algebraic number theory. It is believed to be hard classically, which is of interest for cryptography. In the quantum setting, efficient algorithms were previously known for fields of constant degree. We give a quantum algorithm that is polynomial in the degree of the field and the logarithm of its discriminant. This is achieved by combining three new results. The first is a classical algorithm for computing a basis for certain ideal lattices with doubly exponentially large generators. The second shows that a Gaussian-weighted superposition of lattice points, with an appropriate encoding, can be used to provide a unique representation of a real-valued lattice. The third is an extension of the hidden subgroup problem to continuous groups and a quantum algorithm for solving the HSP over the group Rn.
In this paper, we calculate the upper bound on quantum space complexity of the quantum algorithms proposed by Biasse and Song (SODA'16) for solving class group computation and the principal ideal problem using the reductions to S-unit group computation. We follow the approach of Barbulescu and Poulalion (AFRICACRYPT'23) and the framework given by de Boer, Ducas, and Fehr (EUROCRYPT'20) and Eisentr\"{a}ger, Hallgren, Kitaev, and Song (STOC'14).
In this thesis, we analyse and improve the best known ecient quantum algorithm for solving the Short Principal Ideal Problem (SPIP) in cyclotomic elds, which, given an ideal, determines whether the ideal is principal and outputs a suciently short generator.SPIP is fundamental in cryptography and computational number theory.The standard solution to SPIP can unfold in a two-part process involving the Principal Ideal Problem (PIP) and the Short Generator Problem (SGP).This thesis consists of the following two results.For PIP, we calculate the upper bound on quantum space complexity of the quantum algorithm proposed by Biasse and Song at SODA 2016 (BS) for solving PIP.PIP is the problem that, given an ideal, determines whether the ideal is principal and outputs a generator of the ideal if it is principal.The best known classical algorithm solves PIP in subexponential time, while the BS quantum algorithm nds a generator in polynomial time.Whether the cryptographic systems relying on the hardness of PIP have become insecure depends not only on the existence of polynomial time algorithms solving it but also on whether the algorithms should be implementable.Quantum computers nowadays have only hundreds of qubits, which means that quantum algorithms using too many qubits are not feasible for now.By estimating the qubits used in the BS algorithm, we want to estimate the threat at the moment.
The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems.
In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let ζp be a primitive p-th root of unity, let π=ζp−1, and write q=pt and L=t(p−1). We work over Rq=Zq[ζp]≅Z[ζp]/(πL), where the isomorphism follows from the total ramification identity (p)=(π)p−1. We exploit the resulting π-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo πL,πL−1,…,π. For every fixed prime p and modulus q=pt, our algorithm solves the CCP in time and sample complexity 2Op(lognlogq), using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when q=poly(n). This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting.
However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.
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.