Quantum algorithms for computing short discrete logarithms and factoring RSA integers

DOI10.1007/978-3-319-59879-6_20MaRDI QIDQ1673620zbMATH OpenOpenAlexFDO

Authors Martin Ekerå, Johan Hastad

Publication date 12 September 2018

Full work available at URL https://arxiv.org/abs/1702.00249

zbMATH Keywords

discrete logarithmsfactoringRSAShor's algorithms

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Factorization (11Y05) Quantum algorithms and complexity in the theory of computing (68Q12) Cryptography (94A60)

Abstract: In this paper we generalize the quantum algorithm for computing short discrete logarithms previously introduced by Eker{aa} 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.

Recommendations

• Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
• On computing ord\(_{N}(2)\) and its application
• A low-resource quantum factoring algorithm
• scientific article; zbMATH DE number 5320241
• On post-processing in the quantum algorithm for computing short discrete logarithms

Cited in

(21)

• A low-resource quantum factoring algorithm
• Efficient algorithms for NMR quantum computers with small qubits
• Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
• On post-processing in the quantum algorithm for computing short discrete logarithms
• On computing ord\(_{N}(2)\) and its application
• On completely factoring any integer efficiently in a single run of an order-finding algorithm
• scientific article; zbMATH DE number 5320241 (Why is no real title available?)
• A new quantum algorithm for computing RSA ciphertext period
• Classical and Quantum Algorithms for Exponential Congruences
• Optimized quantum implementation of AES
• Quantum complexity for discrete logarithms and related problems
• Space-efficient and noise-robust quantum factoring
• Space-efficient and noise-robust quantum factoring
• An efficient quantum factoring algorithm
• Computing (N) for an RSA module with a single quantum query
• Reducing the number of qubits in quantum factoring
• RSA quantum cryptanalysis: a thorough exploration of n-bit attacks and emerging factoring techniques
• Quantum algorithm for solving discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves
• Extending Regev's factoring algorithm to compute discrete logarithms
• Reducing the number of qubits in quantum discrete logarithms on elliptic curves
• Parallel spooky pebbling makes Regev factoring more practical

This page was built for publication: Quantum algorithms for computing short discrete logarithms and factoring RSA integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1673620)