Abstract In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multidimensional version of Shor’s algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in
(Z/NZ)× that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such as zero-density estimates. As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm and of subsequent variants.
This thesis contains a collection of efficient quantum algorithms and classical pre- and post-processing algorithms for various number- and group-theoretical problems with concrete cryptanalytical applications. More specifically, the focus is on the integer factoring problem (IFP), the discrete logarithm problem (DLP), and the order-finding problem (OFP), and on certain important variations of these problems. It is for example explained how the OFP and complete IFP may be solved efficiently in a single run of a reduced version of Shor's algorithm for the OFP with very high success probability, as evidenced by a lower bound that is 1 − o(1), how the short DLP in groups of unknown order may be solved efficiently and with an advantage over Shor's algorithm for the DLP (that furthermore requires the order to be known), as evidenced by a lower bound on the single-run success probability that is 1 − o(1), how the RSA IFP may be solved efficiently and with an advantage over Shor's algorithm for the IFP, by reducing the RSA IFP to a short DLP, how the DLP may heuristically be solved efficiently, and with high success probability that is 1 − o(1), in a single run of a reduced version of Shor’s algorithm for the DLP that admits efficient implementation, how the DLP may be solved in groups of unknown order, such as Schnorr groups, by jointly solving an OFP and a DLP at lower overall cost but higher per-run cost compared to first solving the OFP and then the DLP, how tradeoffs — between the number of group operations that are evaluated quantumly and the number of runs that are required — may be achieved in all of the aforementioned algorithms, and how all of the aforementioned algorithms may be simulated efficiently classically, for arbitrary large cryptographically relevant problem instances, when the solution to the instance is known, enabling the number of runs required when performing tradeoffs to be tightly estimated. It is furthermore for example explained how Regev's recent quantum algorithm for the IFP may be extended to the DLP and OFP, yielding i) a reduction in the circuit size and depth by a factor compared to Shor for these problems when working in , for N an n-bit integer, at the expense of performing runs, and ii) slight improvements of Regev's orginal algorithm for the IFP, how the above algorithms may be simulated efficiently classically, for large special-form problem instances that are classically tractable, and that Regev’s post-processing, and the post-processing for our extensions, are robust to an arbitrarily large fraction < 1 of the runs being bad. The above has implications for cryptography based on the intractability of the IFP and DLP — including but not limited to for widely used schemes such as RSA, DSA and Diffie–Hellman. The algorithms in this thesis are all derived from, and make notable improvements to, the seminal works of Shor. Some of the contributions are joint works with other authors.
The discrete logarithm problem (DLP) over finite fields, commonly used in classical cryptography, has no known polynomial-time algorithm on classical computers. However, Shor has provided its polynomial-time algorithm on quantum computers. Nevertheless, there are only few examples simulating quantum circuits that operate on general pairs of modulo
pand order
q. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs of
pand
qup to 32 qubits using a quantum simulator with PRIMEHPC FX700. From this, we obtained and verified values of the success probabilities, which had previously been heuristically analyzed by [Ekerå, arXiv:1905.09084 (2019)]. As a result, the detailed waveform shape of the success probability of Shor's algorithm for solving the DLP, known as a periodic function of order
q, was clarified. Additionally, we generated 1,015 quantum circuits for larger pairs of
pand
q, extrapolated the circuit sizes obtained, and compared them for
p=2048bits between safeprime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same if
pis equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length of
pin the former when using Shor's quantum algorithm. In particular, it was experimentally and theoretically shown that when a basic adder is used in the addition circuit, the cryptographic strength of a Schnorr group with
p=2048bits under Shor's algorithm is almost equivalent to that of a safe-prime group with
p=1024bits.
We generalize our earlier works on computing short discrete logarithms with tradeoffs, and bridge them with Seifert's work on computing orders with tradeoffs, and with Shor's groundbreaking works on computing orders and general discrete logarithms. In particular, we enable tradeoffs when computing general discrete logarithms. Compared to Shor's algorithm, this yields a reduction by up to a factor of two in the number of group operations evaluated quantumly in each run, at the expense of having to perform multiple runs. Unlike Shor's algorithm, our algorithm does not require the group order to be known. It simultaneously computes both the order and the logarithm. We analyze the probability distributions induced by our algorithm, and by Shor's and Seifert's order-finding algorithms, describe how these algorithms may be simulated when the solution is known, and estimate the number of runs required for a given minimum success probability when making different tradeoffs.
Abstract It’s well known that Shor[1] proposed a polynomial time algorithm for prime factorization by using quantum computers. For a given number n, he gave an algorithm for finding the order r of an element x (mod n) instead of giving an algorithm for factoring n directly. The indirect algorithm is feasible because factor-ization can be reduced to finding the order of an element by using randomization[2]. But a point should be stressed that the order of the number must be even. Actually, the restriction can be removed in a particular case. In this paper, we show that factoring RSA modulus (a product of two primes) only needs to find the order of 2, whether it is even or not. Keywords Shor’s quantum algorithm, RSA modulus. 1
Shor's algorithm represents the main threat of quantum computers to cryptography. In order to precisely understand its feasibility, many authors have worked towards reducing its costs, either at the logical level (assuming a fault-tolerant architecture), or at the physical level (taking into account the constraints of envisioned hardware). In particular, recent works by Chevignard et al. (CRYPTO 2024) and Gidney (arXiv 2025) used improved arithmetic to significantly reduce the qubit cost of factoring RSA public keys.
Even more recently, Babbush et al. (arXiv 2026) improved the cost of computing elliptic curve discrete logarithms, with a reduction of a factor 2 to 3 in gate count and qubit count compared to a previous work by Litinski (arXiv 2023). Their result relies on optimized point addition circuits on elliptic curves over prime fields. However they did not reveal their logical quantum circuits, relying instead on a zero-knowledge proof.
In this paper, we detail a quantum logical circuit architecture which gives similar results as Babbush et al., with a slightly higher number of qubits (around 1.5% increase) and a slightly smaller Toffoli gate count (between 6.5% and 10% reduction) for the curve secp256k1. We also give gate counts for a generic variant of the circuit, which is valid for any prime field.