Efficient random search for residue prime sets with small modular deviation (Assumption 1 of the sub-million-qubit quantum factoring estimate)

Gidney's 2025 resource estimate that a 2048-bit RSA integer can be factored in under a week on a fault-tolerant quantum computer with less than a million noisy qubits — the current benchmark figure for the cost of quantumly breaking RSA — rests on an unproven number-theoretic premise stated in the source as Assumption 1: a set $P$ of small primes with $\prod P \ge N^{m}$ and modular deviation $\Delta_N(\prod P) < 2^{-f}$ can be found in expected time $O(2^{f}\cdot\mathrm{poly}(m\cdot\mathrm{len}\,N))$ by randomly varying which primes are included in $P$. This is a fine-scale equidistribution claim about random subset products of small primes modulo $N$, supported experimentally at the RSA-2048 working point but proved for no class of moduli. The problem is to resolve the conjecture: prove the expected-time bound (equivalently, the quantitative equidistribution of random subset products of eligible small primes in $\mathbb{Z}_N^{*}$ at precision $2^{-f}$), or refute it for some family of RSA moduli.

Background

Shor's algorithm factors an RSA modulus $N$ — a product of two large primes, the security anchor of the widely deployed RSA cryptosystem — by quantum period finding: it prepares a superposition over exponents $e$, computes $g^{e}\bmod N$ for a random base $g$ coprime to $N$, and recovers the multiplicative order of $g$ from measurements, from which the factors of $N$ follow with constant probability. The variant of Ekerå and Håstad (PQCrypto 2017) specializes the idea to RSA integers, trading a roughly halved exponent register for a polynomial number of repetitions, which is favorable when qubits are the scarce resource. Because the quantum arithmetic dominates the cost, a long line of work has compressed the modular exponentiation; the most space-efficient version to date is due to Gidney (arXiv:2505.15917, 2025), who estimates that a 2048-bit RSA integer could be factored in less than a week on a fault-tolerant quantum computer with less than a million noisy qubits.

The central arithmetic idea, introduced by Chevignard, Fouque and Schrottenloher (IACR eprint 2024/222) and restructured by Gidney, is approximate residue arithmetic. A residue number system (RNS) represents an integer by its residues modulo a set of coprime small moduli; here the moduli are small primes $p$ (for example 22 bits each), and $L=\prod_{p\in P}p$ is the dynamic range of the system. Rather than computing $V=g^{e}\bmod N$ with $\Theta(\log N)$-bit adders, one computes, for each small prime $p$ in the system, the residue of a factored form of $V$ modulo $p$: a generator $g_p$ modulo $p$ is found, the discrete logarithms $D_{p,k}$ with $g_p^{D_{p,k}} \equiv M_k \pmod{p}$ of the precomputed multipliers $M_k$ (which arise from windowing, i.e. batching exponent bits so that several multiplications become table lookups) are precomputed classically, and the residue $V \bmod p$ is then obtained from a sum of the $D_{p,k}$ followed by a short modular exponentiation with only $\mathrm{len}(p)$ multiplications. So that the result can be reduced modulo $N$, the RNS range must satisfy $\prod P \ge N^{m}$, where $m$ is the number of multiplier factors whose unreduced product (each factor below $N$) must be representable before the final reduction. Gidney's version accumulates modulo $L$ and reduces modulo $N$ only at the end, truncating operands to $f$ kept bits so that the quantum registers are of size $O(\log\log N)$.

The accuracy of this approximation is measured by the modular deviation: for an integer $x$, $\Delta_N(x)=\min(x\bmod N,\,-x\bmod N)/N$ is the normalized distance from $x$ to the nearest multiple of $N$. A series of $A$ truncated additions accumulates total deviation $O(A\cdot 2^{-f})$; the accumulation modulo $L$ adds one further term, because every wraparound of the accumulator modulo $L$ offsets the true value by $L\bmod N$, contributing $O(A\cdot\Delta_N(L))$ in total. Hence the scheme is sound provided $\Delta_N(L) < 2^{-f}$: the product of the chosen small primes must land within a relative window of $2^{-f}$ of a multiple of $N$. Since the primes are chosen by the algorithm designer, this becomes a search problem, and the paper's load-bearing premise is its Assumption 1: randomly varying which small primes are included in $P$ makes $L\bmod N$ behave as if uniformly distributed over $[1,N)$, so a set with $\prod P \ge N^{m}$ and $\Delta_N(\prod P) < 2^{-f}$ is found after about $2^{f}$ samples. The analysis of the period-finding step shows that a constant total deviation suffices, which forces only $f=O(\log\log N)$, so the conjectured search is polynomial-time; the sub-million-qubit estimate, its physical-layer assumptions aside, stands or falls with this unproven number-theoretic claim. Two further constraints shape the search: the primes must not divide any windowed multiplier $M_k$ (otherwise the discrete-log table is undefined), and if too many primes are excluded the prescribed fallback is to increase the prime bit-length $\ell$, enlarging the candidate pool. Crucially, the search must succeed without knowing the factorization of $N$, since it is classical preprocessing for the very modulus one is trying to factor.

Problem Statement

Let $N$ be an integer modulus (in the primary application, an $n$-bit RSA modulus, i.e. a product of two comparably sized primes, with $n=\mathrm{len}\,N$), let $m$ be a positive integer and let $f$ be a positive integer in the source's regime $f=O(\log\log N)$, so that $2^{-f}>1/N$, and for an integer $x$ define the modular deviation $\Delta_N(x)=\min(x\bmod N,\,-x\bmod N)/N$, the normalized distance from $x$ to the nearest multiple of $N$. Fix a pool of small primes (primes of $\ell$ bits, excluding any prime that divides one of the windowed multipliers of the exponentiation), and for a subset $P$ of the pool write $L=\prod_{p\in P}p$. Gidney's Assumption 1 asserts that a subset $P$ with $\prod P \ge N^{m}$ and $\Delta_N(\prod P) < 2^{-f}$ can be found in expected time $O(2^{f}\cdot\mathrm{poly}(m\cdot\mathrm{len}\,N))$ by randomly varying which primes are included in $P$. As the source leaves the probability law behind this random variation of $P$ implicit, the sampling model is fixed for this problem as follows: each eligible prime is included in $P$ independently with probability $1/2$, conditioned on $\prod P \ge N^{m}$. Both the expected-time bound of branch (a) and the refutation of branch (b) are to be established under this model. Resolve this conjecture in one of the following forms.

(a) Prove the expected-time bound, unconditionally, for all RSA moduli $N$ — a product of two comparably sized primes, the class of moduli to which the source applies the assumption — whose eligible pool admits a subset $P$ with $\prod P \ge N^{m}$; equivalently, establish that random subset products of the eligible small primes are equidistributed modulo $N$ at the quantitative precision needed, so that a sample satisfies $\Delta_N(\prod P) < 2^{-f}$ with probability $\Theta(2^{-f})$.

(b) Refute the conjecture by exhibiting an RSA modulus $N$ — a product of two comparably sized primes, the class of moduli to which the source applies the assumption — or a provable infinite family of RSA moduli, for which no eligible $P$ exists, or for which the random search requires asymptotically more than $O(2^{f}\cdot\mathrm{poly}(m\cdot\mathrm{len}\,N))$ expected time; the refutation must account for the source's freedom to enlarge the prime bit-length $\ell$ (and hence the pool) when the eligible pool is over-constrained.

In the intended application $f=O(\log\log N)$, so a resolution of form (a) upgrades the classical preprocessing of the sub-million-qubit factoring pipeline from conjectural to rigorously polynomial-time; a resolution of form (b) would undermine the space savings of the entire algorithm and force its arithmetic to be reworked.

References

1. Craig Gidney, "How to factor 2048 bit RSA integers with less than a million noisy qubits", arXiv:2505.15917 (2025), DOI: 10.48550/arxiv.2505.15917, https://arxiv.org/abs/2505.15917
2. Clémence Chevignard, Pierre-Alain Fouque, André Schrottenloher, "Reducing the Number of Qubits in Quantum Factoring", Cryptology ePrint Archive, Paper 2024/222 (2024), https://eprint.iacr.org/2024/222
3. Craig Gidney, Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", Quantum 5, p. 433 (2021), DOI: 10.22331/q-2021-04-15-433, https://arxiv.org/abs/1905.09749
4. Martin Ekerå, Johan Håstad, "Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers", in Post-Quantum Cryptography (PQCrypto 2017), Lecture Notes in Computer Science, Springer, pp. 347–363 (2017), DOI: 10.1007/978-3-319-59879-6_20, https://link.springer.com/chapter/10.1007/978-3-319-59879-6_20
5. Tian Xue, Jacob P. Covey, "Factoring $2048$ bit RSA integers with a half-million-qubit modular atomic processor", arXiv:2605.03951 (2026), DOI: 10.48550/arxiv.2605.03951, https://arxiv.org/abs/2605.03951
6. Paul Webster, Lucas Berent, Omprakash Chandra, Evan T. Hockings, Nouédyn Baspin, Felix Thomsen, Samuel C. Smith, Lawrence Z. Cohen, "The Pinnacle Architecture: Reducing the cost of breaking RSA-2048 to 100 000 physical qubits using quantum LDPC codes", arXiv:2602.11457 (2026), DOI: 10.48550/arxiv.2602.11457, https://arxiv.org/abs/2602.11457
7. Clémence Chevignard, Pierre-Alain Fouque, André Schrottenloher, "Reducing the Number of Qubits in Quantum Discrete Logarithms on Elliptic Curves", Cryptology ePrint Archive, Paper 2026/280 (2026), https://eprint.iacr.org/2026/280
8. Alessio Paviglianiti, Matteo Seclì, Emanuele Tirrito, Vincenzo Savona, "The true cost of factoring: Linking magic and number-theoretic complexity in Shor's algorithm", arXiv:2605.05347 (2026), DOI: 10.48550/arxiv.2605.05347, https://arxiv.org/abs/2605.05347