Quantumly Computing S-unit Groups in Quantified Polynomial Time and Space

Koen de Boer; Joël Felderhoff

Paper 2025/1825

Quantumly Computing S-unit Groups in Quantified Polynomial Time and Space

Koen de Boer

Joël Felderhoff

, King's College London

Abstract

We present a novel analysis of a quantum algorithm computing the S-unit group for a number field from Eisenträger et al. [EHKS14a] and Biasse and Song [BS16]. We prove that this quantum algorithm runs within polynomial time, where we explicitly quantify the polynomials of the quantum gate and memory complexity (under GRH). We do so by carefully analyzing an implementation of an Continuous Hidden Subgroup Problem (CHSP) oracle function whose period is the (logarithm of the) S-unit group, and provide it to an CHSP-solving algorithm as in [BDF19]. Our analysis is novel due to minimizing the use of the quantum memory-inefficient LLL-reduction, by resorting to strategically chosen precomputations of approximations of high powers of prime ideals. Additionally, we provide a new quantum algorithm computing a discrete Gaussian superposition analogue of the GPV algorithm by Gentry et al. [GPV08]. Lastly, we include a full and rigorous numerical analysis of all parts of the oracle-function computing algorithm, allowing to use fixed-point precision arithmetic and thus to precisely quantify the run-time and memory.

Note: Changelog 22/10/2025: - Added appendix "Postprocessing: from an approximate basis of the log-S-units to the compact representation of S-units" - Added Joël Felderhoff's grant number Changelog 13/02/2026 (pdf submitted on 21/02/2026 due to error) - Added the proof of Lemma K.1 (reduction from CHSP over Z^k \times R^m to R^{k+m} - Added a discussion on the cryptographic impact - Fixed typos

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: Quantum CHSP Lattice Ideal SVP PIP Class Group S Units GPV Gaussian Number Theory Algebraic Number Theory
Contact author(s): kboer research @ gmail com
joel felderhoff @ kcl ac uk
History: 2026-02-21: last of 3 revisions; 2025-10-03: received; See all versions
Short URL: https://ia.cr/2025/1825
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1825,
      author = {Koen de Boer and Joël Felderhoff},
      title = {Quantumly Computing S-unit Groups in Quantified Polynomial Time and Space},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1825},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1825}
}