{"id":"arxiv/2609.34996","url":"https://arxiv.org/abs/2609.34996","tags":["quant-ph","cs.CR"],"score":0,"title":"Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli","domain":"quant-ph","source":"arxiv","authors":["Mathias Boucher","Pierre-Alain Fouque","Yixin Shen"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}