Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.29453

Quantum Algorithms for Modular Factorials

Yann Tal

quant-phcs.CCSubmitted Jul 31, 2026• Announced Aug 3, 2026• 0 citations
arXivHTMLPDF

Abstract

We give a bounded-error quantum algorithm that, given a prime $p$, a divisor $q\mid(p-1)$, and an integer $0<n<p$, computes $n!\bmod p$ in expected time $\widetilde{O}(q^c+\sqrt{p/q})$ for some absolute constant $c\ge 1$. When $p-1$ has a divisor of size $q\approx p^{1/(2c+1)}$, this gives the exponent $c/(2c+1)<1/2$. To our knowledge, this is the first algorithm to break the exponent $1/2$ barrier for modular factorials under such a divisor promise. The main technical ingredient is a quantum algorithm that reconstructs the relevant Jacobi sum exactly in compact algebraic form, with polynomial dependence on $q$ and $\log p$. We further extend the same asymptotic bound to the computation of $n!\bmod p^2$, uniformly over $0\le n<p^2$. At $n=p-1$, this determines the Wilson quotient $\frac{(p-1)!+1}{p}\pmod p$. We conjecture that the condition $q\mid(p-1)$ is a technical limitation of the present method rather than an inherent obstruction, and that a uniform quantum algorithm exists for all primes.

Comments
41 pages

Related papers

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth

Gregory D. Kahanamoku–Meyer, Seyoon Ragavan, Vinod Vaikuntanathan +1 more

We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). Most notably, we factor $n$-bit integers of the form $P^2 Q$ with $\log Q = Θ(n^a)$ for $a \in (2/3, 1)$ in space and depth sublinear in n (specifically, $\tilde{O}(\log Q)$) using $\tilde{O}(n)$ quantum gates; for these integers, no known classical algorithms exploit the relatively small size of $Q$ to run asymptotically faster than general-purpose factoring algorithms. To our knowledge, this is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem. Our circuit builds on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du, and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of $A$ mod $B$, in the regime where $B$ is classical and much larger than $A$. Our circuit for computing the Jacobi symbol generalizes to related problems such as computing the greatest common divisor and modular inverses, and thus could be of independent interest.

arXiv:2412.12558•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•2 citations

Deterministic Prime Bases for Regev's Algorithm

Steven Tolbert

Regev's quantum factoring algorithm reduces the number of gates per quantum call, but its correctness for the original deterministic prime bases rests on a number-theoretic assumption. We prove that the first ⌈√n⌉ primes work unconditionally for almost all n-bit composite inputs, including almost all composite inputs surviving trial division by those primes. The algorithm retains Regev's original asymptotic gate count per quantum call. A separate theorem covers balanced RSA moduli under three explicit sampling laws. The exceptional input proportion is Θ(2^{-⌈√n⌉}); a population of this order admits no useful relation at any length. On each remaining input, Regev's algorithm finds a nontrivial divisor with constant probability using ⌈√n⌉+4 quantum calls of O(n^{3/2} log n) gates each. The main geometric lemma extracts a useful relation from an earlier successive minimum, determined by the dimension of a quotient of the relation lattice. Prime-divisor counting then gives useful-relation lengths 2^{(3/2+o(1))√n} for general inputs and 2^{(9/2+o(1))√n} for RSA. Both main theorems and finite RSA useful-vector bounds are formally verified in Lean 4; the formalization is archived at https://doi.org/10.5281/zenodo.23407163.

•Oct 16, 2026•0 citations

Computing $φ(N)$ for an RSA module with a single quantum query

Luis Victor Dieulefait, Jorge Jiménez Urroz

In this paper we give a polynomial time algorithm to compute $φ(N)$ for an RSA module $N$ using as input the order modulo $N$ of a randomly chosen integer. This provides a new insight in the very important problem of factoring an RSA module with extra information. In fact, the algorithm is extremely simple and consists only on a computation of a greatest common divisor, two multiplications and a division. The algorithm works with a probability of at least $1-\frac{1}{N^{1/2-ε}}$, where $ε$ is any small positive constant.

arXiv:2406.04061•Jun 6, 2024•0 citations

Quantum polynomial-time conjugacy in metabelian groups

Alexei Miasnikov, Alexander Ushakov

We prove that the conjugacy problem in finitely presented metabelian groups with a fixed number of generators is solvable in bounded-error quantum polynomial time, uniformly in the defining relations of the group. Both the group presentation and the words representing the elements are part of the input. The main ingredient is a quantum polynomial-time algorithm for computing all multiplicative relations among a fixed number of units in a commutative affine $\mathbb Z$-algebra presented with a fixed number of variables. The algorithm reduces the problem to computations in finite-dimensional algebras over $\mathbb Q$ and finite rings by identifying the lattice of exponent vectors whose corresponding products are algebraic over the coefficient field. An effective arithmetic splitting combines the rational and finite-ring computations. The proof uses effective bounds for polynomial equations, algorithms for finite-dimensional commutative algebras, quantum integer factorization, and finite abelian hidden-subgroup algorithms.

arXiv:2610.27250•Oct 19, 2026•0 citations

Exact quantum factoring over a fixed finite gate set

OpenAI

We give a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer N\ge2 with probability one. A fixed finite set of bounded-arity gates suffices, and both the gate count and the number of qubits have polynomial worst-case bounds in the input length.

•Oct 6, 2026•0 citations

Space-Efficient and Noise-Robust Quantum Factoring

Seyoon Ragavan, Vinod Vaikuntanathan

We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires $O(n^{3/2})$ qubits and $O(n^{3/2} \log n)$ gates, while Shor's circuit requires $O(n^2 \log n)$ gates but only $O(n \log n)$ qubits. As with Regev, to factor an $n$-bit integer $N$, we run our circuit independently $O(\sqrt{n})$ times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling in-place quantum-quantum modular multiplication. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all $\approx \sqrt{n}$ runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.

arXiv:2310.00899•Oct 2, 2023•2 citations
We give a bounded-error quantum algorithm that, given a prime ppp, a divisor q∣(p−1)q\mid(p-1)q∣(p−1), and an integer 0<n<p0<n<p0<n<p, computes n! mod pn!\bmod pn!modp in expected time O~(qc+p/q)\widetilde{O}(q^c+\sqrt{p/q})O(qc+p/q​) for some absolute constant c≥1c\ge 1c≥1. When p−1p-1p−1 has a divisor of size q≈p1/(2c+1)q\approx p^{1/(2c+1)}q≈p1/(2c+1), this gives the exponent c/(2c+1)<1/2c/(2c+1)<1/2c/(2c+1)<1/2. To our knowledge, this is the first algorithm to break the exponent 1/21/21/2 barrier for modular factorials under such a divisor promise. The main technical ingredient is a quantum algorithm that reconstructs the relevant Jacobi sum exactly in compact algebraic form, with polynomial dependence on qqq and log⁡p\log plogp. We further extend the same asymptotic bound to the computation of n! mod p2n!\bmod p^2n!modp2, uniformly over 0≤n<p20\le n<p^20≤n<p2. At n=p−1n=p-1n=p−1, this determines the Wilson quotient (p−1)!+1p(modp)\frac{(p-1)!+1}{p}\pmod pp(p−1)!+1​(modp). We conjecture that the condition q∣(p−1)q\mid(p-1)q∣(p−1) is a technical limitation of the present method rather than an inherent obstruction, and that a uniform quantum algorithm exists for all primes.
We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). Most notably, we factor nnn-bit integers of the form P2QP^2 QP2Q with log⁡Q=Θ(na)\log Q = Θ(n^a)logQ=Θ(na) for a∈(2/3,1)a \in (2/3, 1)a∈(2/3,1) in space and depth sublinear in n (specifically, O~(log⁡Q)\tilde{O}(\log Q)O~(logQ)) using O~(n)\tilde{O}(n)O~(n) quantum gates; for these integers, no known classical algorithms exploit the relatively small size of QQQ to run asymptotically faster than general-purpose factoring algorithms. To our knowledge, this is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem. Our circuit builds on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du, and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of AAA mod BBB, in the regime where BBB is classical and much larger than AAA. Our circuit for computing the Jacobi symbol generalizes to related problems such as computing the greatest common divisor and modular inverses, and thus could be of independent interest.
Regev's quantum factoring algorithm reduces the number of gates per quantum call, but its correctness for the original deterministic prime bases rests on a number-theoretic assumption. We prove that the first ⌈√n⌉ primes work unconditionally for almost all n-bit composite inputs, including almost all composite inputs surviving trial division by those primes. The algorithm retains Regev's original asymptotic gate count per quantum call. A separate theorem covers balanced RSA moduli under three explicit sampling laws. The exceptional input proportion is Θ(2^{-⌈√n⌉}); a population of this order admits no useful relation at any length. On each remaining input, Regev's algorithm finds a nontrivial divisor with constant probability using ⌈√n⌉+4 quantum calls of O(n^{3/2} log n) gates each. The main geometric lemma extracts a useful relation from an earlier successive minimum, determined by the dimension of a quotient of the relation lattice. Prime-divisor counting then gives useful-relation lengths 2^{(3/2+o(1))√n} for general inputs and 2^{(9/2+o(1))√n} for RSA. Both main theorems and finite RSA useful-vector bounds are formally verified in Lean 4; the formalization is archived at https://doi.org/10.5281/zenodo.23407163.
Computing φ(N)φ(N)φ(N) for an RSA module with a single quantum query
In this paper we give a polynomial time algorithm to compute φ(N)φ(N)φ(N) for an RSA module NNN using as input the order modulo NNN of a randomly chosen integer. This provides a new insight in the very important problem of factoring an RSA module with extra information. In fact, the algorithm is extremely simple and consists only on a computation of a greatest common divisor, two multiplications and a division. The algorithm works with a probability of at least 1−1N1/2−ε1-\frac{1}{N^{1/2-ε}}1−N1/2−ε1​, where εεε is any small positive constant.
We prove that the conjugacy problem in finitely presented metabelian groups with a fixed number of generators is solvable in bounded-error quantum polynomial time, uniformly in the defining relations of the group. Both the group presentation and the words representing the elements are part of the input. The main ingredient is a quantum polynomial-time algorithm for computing all multiplicative relations among a fixed number of units in a commutative affine Z\mathbb ZZ-algebra presented with a fixed number of variables. The algorithm reduces the problem to computations in finite-dimensional algebras over Q\mathbb QQ and finite rings by identifying the lattice of exponent vectors whose corresponding products are algebraic over the coefficient field. An effective arithmetic splitting combines the rational and finite-ring computations. The proof uses effective bounds for polynomial equations, algorithms for finite-dimensional commutative algebras, quantum integer factorization, and finite abelian hidden-subgroup algorithms.
We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using O(nlog⁡n)O(n \log n)O(nlogn) qubits and O(n3/2log⁡n)O(n^{3/2} \log n)O(n3/2logn) gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires O(n3/2)O(n^{3/2})O(n3/2) qubits and O(n3/2log⁡n)O(n^{3/2} \log n)O(n3/2logn) gates, while Shor's circuit requires O(n2log⁡n)O(n^2 \log n)O(n2logn) gates but only O(nlog⁡n)O(n \log n)O(nlogn) qubits. As with Regev, to factor an nnn-bit integer NNN, we run our circuit independently O(n)O(\sqrt{n})O(n​) times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling in-place quantum-quantum modular multiplication. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all ≈n\approx \sqrt{n}≈n​ runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.