Quantum algorithms for computing short discrete logarithms and factoring RSA integers

Abstract

In this paper we generalize the quantum algorithm for computing short discrete logarithms previously introduced by Ekerå so as to allow for various tradeoffs between the number of times that the algorithm need be executed on the one hand, and the complexity of the algorithm and the requirements it imposes on the quantum computer on the other hand. Furthermore, we describe applications of algorithms for computing short discrete logarithms. In particular, we show how other important problems such as those of factoring RSA integers and of finding the order of groups under side information may be recast as short discrete logarithm problems. This immediately gives rise to an algorithm for factoring RSA integers that is less complex than Shor's general factoring algorithm in the sense that it imposes smaller requirements on the quantum computer. In both our algorithm and Shor's algorithm, the main hurdle is to compute a modular exponentiation in superposition. When factoring an n bit integer, the exponent is of length 2n bits in Shor's algorithm, compared to slightly more than n/2 bits in our algorithm.

Cited by in corpus (18)

• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Review of Distributed Quantum Computing. From single QPU to High Performance Quantum Computing
• Towards security recommendations for public-key infrastructures for production environments in the post-quantum era
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Gauge Theory Couplings on Anisotropic Lattices
• Networked Quantum Services
• Extending Regev's factoring algorithm to compute discrete logarithms
• The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers
• Quantum Complexity for Discrete Logarithms and Related Problems
• Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
• On the success probability of quantum order finding
• A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography
• The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
• Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems
• Simulation of Shor algorithm for discrete logarithm problems with comprehensive pairs of modulo p and order q
• On completely factoring any integer efficiently in a single run of an order finding algorithm
• Tight Success Probabilities for Quantum Period Finding and Phase Estimation
• Quantum Algorithms for Discrete Log Require Precise Rotations