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•5 citations

Quantum probabilistic subroutines and problems in number theory

A. Carlini, Akio Hosoya

We present a quantum version of the classical probabilistic algorithms as studied by Rabin. The quantum algorithm is based on the essential use of Grover's operator for the quantum search of a database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the counting algorithm originally introduced by Brassard et al. One of the main features of our quantum probabilistic algorithm is its full unitarity and reversibility, which would make its use possible as part of larger and more complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problems in number theory, such as the test of the primality of an integer, the so called prime number theorem, and Hardy and Littlewood's conjecture about the asymptotic number of representations of an even integer as a sum of two primes.

arXiv:quant-ph/9907020•Physical Review A•Aug 18, 2000•12 citations

Sharp probability estimates for Shor's order-finding algorithm

Paul Bourdon, H. T. Williams

Let N be a (large positive integer, let b > 1 be an integer relatively prime to N, and let r be the order of b modulo N. Finally, let QC be a quantum computer whose input register has the size specified in Shor's original description of his order-finding algorithm. We prove that when Shor's algorithm is implemented on QC, then the probability P of obtaining a (nontrivial) divisor of r exceeds 0.7 whenever N exceeds 2^{11}-1 and r exceeds 39, and we establish that 0.7736 is an asymptotic lower bound for P. When N is not a power of an odd prime, Gerjuoy has shown that P exceeds 90 percent for N and r sufficiently large. We give easily checked conditions on N and r for this 90 percent threshold to hold, and we establish an asymptotic lower bound for P of (2/Pi) Si(4Pi), about .9499, in this situation. More generally, for any nonnegative integer q, we show that when QC(q) is a quantum computer whose input register has q more qubits than does QC, and Shor's algorithm is run on QC(q), then an asymptotic lower bound on P is (2/Pi) Si(2^(q+2) Pi) (if N is not a power of an odd prime). Our arguments are elementary and our lower bounds on P are carefully justified.

arXiv:quant-ph/0607148•Quantum Information and Computation•Jul 21, 2006•14 citations

The quantum Euclid algorithm and its application to factoring

Asma Al-Qasimi, Daniel F. V. James

We present a quantum implementation of the Euclid algorithm for calculating the Greatest Common Divisor when one of the integers involved is a compound of two odd-valued primes. We discuss a possible application to the quantum factoring problem, for which modular exponentiation is no longer required, and the factors are revealed directly by measurements, although the method does not scale for large numbers in a favourable manner.

arXiv:2611.15387•EPJ Quantum Technology•Nov 9, 2026•0 citations

Probability estimates for Shor's algorithm

Paul Bourdon, H. T. Williams

Let N be a (large) positive integer, let b be an integer satisfying 1< b < N that is relatively prime to N, and let r be the order of b modulo N. Finally, let QC be a quantum computer whose input register has the size specified in Shor's original description of his order-finding algorithm. In this paper, we analyze the probability that a single run of the quantum component of the algorithm yields useful information---a nontrivial divisor of the order sought. We prove that when Shor's algorithm is implemented on QC, then the probability P of obtaining a (nontrivial) divisor of $r$ exceeds $.7$ whenever N \ge 2^{11} and r\ge 40, and we establish that $.7736$ is an asymptotic lower bound for $P$. When $N$ is not a power of an odd prime, Gerjuoy has shown that $P$ exceeds 90 percent for $N$ and $r$ sufficiently large. We give easily checked conditions on N and r for this 90 percent threshold to hold, and we establish an asymptotic lower bound for $P$ of 2\Si(4\pi)/\pi ~0.9499 in this situation. More generally, for any nonnegative integer $q$, we show that when QC(q) is a quantum computer whose input register has $q$ more qubits than does QC, and Shor's algorithm is run on QC(q), then an asymptotic lower bound on P is 2\Si(2^{q+2}\pi)/\pi (if N is not a power of an odd prime). Our arguments are elementary and our lower bounds on P are carefully justified.

Quantum Information and Computation•Jul 1, 2007•3 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
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.
We present a quantum version of the classical probabilistic algorithms as studied by Rabin. The quantum algorithm is based on the essential use of Grover's operator for the quantum search of a database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the counting algorithm originally introduced by Brassard et al. One of the main features of our quantum probabilistic algorithm is its full unitarity and reversibility, which would make its use possible as part of larger and more complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problems in number theory, such as the test of the primality of an integer, the so called prime number theorem, and Hardy and Littlewood's conjecture about the asymptotic number of representations of an even integer as a sum of two primes.
Let N be a (large positive integer, let b > 1 be an integer relatively prime to N, and let r be the order of b modulo N. Finally, let QC be a quantum computer whose input register has the size specified in Shor's original description of his order-finding algorithm. We prove that when Shor's algorithm is implemented on QC, then the probability P of obtaining a (nontrivial) divisor of r exceeds 0.7 whenever N exceeds 2^{11}-1 and r exceeds 39, and we establish that 0.7736 is an asymptotic lower bound for P. When N is not a power of an odd prime, Gerjuoy has shown that P exceeds 90 percent for N and r sufficiently large. We give easily checked conditions on N and r for this 90 percent threshold to hold, and we establish an asymptotic lower bound for P of (2/Pi) Si(4Pi), about .9499, in this situation. More generally, for any nonnegative integer q, we show that when QC(q) is a quantum computer whose input register has q more qubits than does QC, and Shor's algorithm is run on QC(q), then an asymptotic lower bound on P is (2/Pi) Si(2^(q+2) Pi) (if N is not a power of an odd prime). Our arguments are elementary and our lower bounds on P are carefully justified.
Let N be a (large) positive integer, let b be an integer satisfying 1< b < N that is relatively prime to N, and let r be the order of b modulo N. Finally, let QC be a quantum computer whose input register has the size specified in Shor's original description of his order-finding algorithm. In this paper, we analyze the probability that a single run of the quantum component of the algorithm yields useful information---a nontrivial divisor of the order sought. We prove that when Shor's algorithm is implemented on QC, then the probability P of obtaining a (nontrivial) divisor of rrr exceeds .7.7.7 whenever N \ge 2^{11} and r\ge 40, and we establish that .7736.7736.7736 is an asymptotic lower bound for PPP. When NNN is not a power of an odd prime, Gerjuoy has shown that PPP exceeds 90 percent for NNN and rrr sufficiently large. We give easily checked conditions on N and r for this 90 percent threshold to hold, and we establish an asymptotic lower bound for PPP of 2\Si(4\pi)/\pi ~0.9499 in this situation. More generally, for any nonnegative integer qqq, we show that when QC(q) is a quantum computer whose input register has qqq more qubits than does QC, and Shor's algorithm is run on QC(q), then an asymptotic lower bound on P is 2\Si(2^{q+2}\pi)/\pi (if N is not a power of an odd prime). Our arguments are elementary and our lower bounds on P are carefully justified.
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.