Unconditional quantum generic ring model lower bounds for order finding and integer factoring

Hhan (2024) introduced the quantum generic ring model (QGRM), where a quantum algorithm computes in a ring isomorphic to $\mathbb{Z}_N$ with the modulus $N$ hidden, and proved two logarithmic ring-operation lower bounds: one for order finding when $N$ is a product of safe primes under an unproven counting assumption on safe primes, and one for factoring algorithms whose output integer is relatively small. Both bounds carry auxiliary restrictions that stand between them and unconditional evidence that quantum factoring requires $\Omega(\log N)$ ring operations: the order-finding bound fails for general prime moduli and relies on a Sophie Germain-type counting conjecture, and the factoring bound is vacuous for outputs of the magnitude produced by Shor's algorithm, $Z=a^{r/2}-1$. The problem is to remove both restrictions — prove comparable lower bounds for general prime moduli (uniform $n$-bit primes) without the counting assumption, and for factoring with unrestricted output size — or to refute them by exhibiting generic algorithms that escape the bounds.

Background

The generic group model (GGM), introduced by Shoup (1997), formalizes algorithms that treat group elements as opaque encodings and interact with them only through a group-operation oracle and equality tests; in this model any discrete-logarithm algorithm in a prime-order group needs $\Omega(\sqrt{q})$ operations. The generic ring model extends the idea to the ring $\mathbb{Z}_N$: Aggarwal and Maurer (2009) showed that when $N$ is known, breaking RSA generically is equivalent to factoring. In the quantum setting, Hhan, Yamakawa, and Yun (2023; CRYPTO 2024) defined the quantum generic group model (QGGM) and proved that any generic quantum algorithm for the discrete logarithm in a prime-order group needs $\Omega(\log |G|)$ group operations, showing that Shor's algorithm is asymptotically optimal among generic quantum algorithms.

Hhan (2024) introduced the quantum generic ring model (QGRM) and proved its lower bounds through compression arguments: a successful algorithm is converted into a communication protocol that transmits information (such as the factorization of $N$) more cheaply than information-theoretic compression lemmas allow. In the QGRM the ring is isomorphic to $\mathbb{Z}_N$ with $N=pq$, and — unlike the classical generic ring model — the modulus $N$ is not given to the algorithm; the algorithm holds element registers and qubit registers, with element gates that coherently address up to $t+w$ element registers (as governed by the parameters $t$ and $w$), applies coherent gates for ring addition, subtraction, product-addition, inversion, and equality tests, and may use certain classical preprocessing. The cost metric is the number $Q$ of element gates (ring operations). Order finding means outputting $\operatorname{ord}_N(x)$, the least $e\ge 1$ with $x^e \equiv 1 \pmod N$; it is the core subroutine of Shor's factoring algorithm, which computes $r=\operatorname{ord}_N(a)$ and then a factor of $N$ from $a^{r/2}\mp 1$. Regev's (2023) factoring algorithm is also captured by a modified variant whose output is a small integer sharing a factor with $N$.

Two theorems anchor the QGRM. Theorem 6.1: if $p,q$ are random $n$-bit safe primes — primes $p$ with $(p-1)/2$ also prime, the value $(p-1)/2$ being a Sophie Germain prime — and $N=pq$, then, assuming the number of $n$-bit safe primes is at least $C\cdot 2^n/n^2$ (a variant of the conjecture that safe primes below $N$ number $\Theta(N/\log^2 N)$), any QGRM order-finding algorithm succeeds only with probability exponentially small in $n$ unless $Q=\Omega(n)=\Omega(\log N)$. The proof exploits that for safe primes $p=2p'+1$, $q=2q'+1$, the order of a random $x$ equals $(p-1)(q-1)/2=2p'q'$ or $(p-1)(q-1)/4=p'q'$ with probability $1-O(1/p)$, from which $(p,q)$ can be recovered by solving a quadratic — so a successful order-finding algorithm compresses the $2n$-bit description of $(p,q)$, and the interactive compression lemma of Bab Hadiashar, Nayak, and Renner (2018) bounds achievable compression as a function of $Q$. Theorem 6.2: any QGRM algorithm that outputs a plain integer $Z$ with $1<\gcd(Z,N)<N$ (computed without modular reduction, since $N$ is hidden) succeeds with probability $O(n\log Z\,(2tw)^{2Q}/2^{n})$, a bound that is meaningful only when $\log Z$ is not too large; it covers the modified Regev algorithm but not Shor's algorithm, whose natural output $Z=a^{r/2}-1$ has bit length as large as about $nN/2$, where the bound is vacuous. These are the first lower-bound results suggesting that quantum factoring needs a logarithmic number of ring operations in an idealized ring model — but both carry auxiliary restrictions, and the source paper itself flags that its bound 'cannot apply to Shor's algorithm in general'.

Problem Statement

In the quantum generic ring model (QGRM) of Hhan (2024, Section 6.1) — a ring isomorphic to $\mathbb{Z}_N$ with $N=pq$ hidden from the algorithm, element and equality gates acting on element registers, classical preprocessing allowed, and cost measured as the number $Q$ of ring operations — settle the following two lower-bound questions without the auxiliary restrictions of the source, or refute them. In both parts the target lower bound is the source's $Q=\Omega(\log N/\log(2tw))$, i.e., $Q=\Omega(\log N)$ for constant model parameters $t,w$:

(a) Order finding for general moduli: prove that any QGRM algorithm that, given a random $x\in\mathbb{Z}_N$ with $N=pq$ and $p,q$ uniform independent $n$-bit primes, not necessarily safe — the distribution $\mathcal{D}_{\mathrm{prime}}^{(n)}$ of the source's Theorem 6.2 — outputs $\operatorname{ord}_N(x)$ with non-negligible probability must use $Q=\Omega(\log N)$ ring operations, with no assumption about the count of safe primes or Sophie Germain primes and no use of the special order structure of safe-prime moduli; or exhibit such an algorithm achieving $o(\log N)$ ring operations for this same distribution.

(b) Factoring with unrestricted output: prove that any QGRM algorithm that outputs any plain integer $Z$ (with no restriction on the magnitude of $Z$) satisfying $1<\gcd(Z,N)<N$ must use $Q=\Omega(\log N)$ ring operations — in particular covering outputs of the magnitude produced by Shor's algorithm, $Z=a^{r/2}-1$; or refute this by exhibiting a QGRM algorithm that outputs such a $Z$ with $o(\log N)$ ring operations.

The two parts jointly determine whether the QGRM yields unconditional evidence that any generic quantum factoring procedure — including Shor's algorithm itself, beyond its small-output modified variants — requires a logarithmic number of ring operations. A complete answer resolves both parts; a resolution of either part alone is meaningful progress on the shared objective.

References

1. Minki Hhan. A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More. EUROCRYPT 2025 (DOI: 10.1007/978-3-031-91098-2_13); IACR ePrint 2024/268; arXiv:2402.11269 (2024). DOI: 10.48550/arXiv.2402.11269. https://arxiv.org/abs/2402.11269
2. Henry Corrigan-Gibbs, Alexandra Henzinger, David J. Wu. The Structured Generic-Group Model. EUROCRYPT 2026, IACR ePrint 2026/384. DOI: 10.1007/978-3-032-25330-9_4. https://eprint.iacr.org/2026/384
3. Minki Hhan, Takashi Yamakawa, Aaram Yun. Quantum Complexity for Discrete Logarithms and Related Problems. CRYPTO 2024 (DOI: 10.1007/978-3-031-68391-6_1); arXiv:2307.03065 (2023). DOI: 10.48550/arXiv.2307.03065. https://arxiv.org/abs/2307.03065
4. Oded Regev. An Efficient Quantum Factoring Algorithm. arXiv:2308.06572 (2023). DOI: 10.48550/arXiv.2308.06572. https://arxiv.org/abs/2308.06572
5. Divesh Aggarwal, Ueli Maurer. Breaking RSA Generically is Equivalent to Factoring. EUROCRYPT 2009, IACR ePrint 2008/260. https://eprint.iacr.org/2008/260
6. Victor Shoup. Lower Bounds for Discrete Logarithms and Related Problems. EUROCRYPT 1997. DOI: 10.1007/3-540-69053-0_18. https://doi.org/10.1007/3-540-69053-0_18
7. Shima Bab Hadiashar, Ashwin Nayak, Renato Renner. Communication Complexity of One-Shot Remote State Preparation. IEEE Transactions on Information Theory 64(7):4709-4728 (2018). DOI: 10.1109/TIT.2018.2811509. https://doi.org/10.1109/TIT.2018.2811509
8. Paul Kirchner, Pierre-Alain Fouque. Getting Rid of Linear Algebra in Number Theory Problems. IACR ePrint 2020/1619 (2020). https://eprint.iacr.org/2020/1619