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:2112.11358 · Security and Communication Networks

Feasibility Analysis of Cracking RSA with Improved Quantum Circuits of the Shor’s Algorithm

Xia Liu, Huan Yang, Li Yang

Published Nov 24, 2023• 6 citations
arXivHTMLPDF

Abstract

Since the RSA public key cryptosystem was proposed, it has been widely used because of its strong security. Although the proposal of the Shor’s algorithm offers hope for cracking RSA, it is debatable whether the algorithm can actually pose a threat in practice. From the perspective of the quantum circuit of the Shor’s algorithm, we analyse the feasibility of cracking RSA with improved quantum circuits using an ion-trap quantum computer. We present an improved quantum circuit for the modular exponentiation of a constant, which is the most expensive operation in Shor’s algorithm for integer factorization. Whereas previous studies mostly focused on minimizing the number of qubits or the depth of the circuit, we minimize the number of CNOTs, which greatly affects the time to run the algorithm on an ion-trap quantum computer. First, we give the implementation of the basic arithmetic with the lowest known number of CNOTs and the construction of an improved modular exponentiation of a constant by accumulating intermediate data and using a windowing technique. Then, we precisely estimate the number of improved quantum circuits needed to perform the Shor’s algorithm for factoring an n -bit integer, which is 217 n 3 / log 2 n + 4 n 2 + n . We analyse the running time and feasibility of the Shor’s algorithm on an ion-trap quantum computer according to the number of CNOTs. Finally, we discussed the lower bound of the number of CNOTs needed to implement the Shor’s algorithm.

DOI
10.1155/2023/2963110

Related papers

Minimizing CNOT-count in quantum circuit of the extended Shor’s algorithm for ECDLP

Xia Liu, Huan Yang, Li Yang

Abstract The elliptic curve discrete logarithm problem (ECDLP) is a popular choice for cryptosystems due to its high level of security. However, with the advent of the extended Shor’s algorithm, there is concern that ECDLP may soon be vulnerable. While the algorithm does offer hope in solving ECDLP, it is still uncertain whether it can pose a real threat in practice. From the perspective of the quantum circuits of the algorithm, this paper analyzes the feasibility of cracking ECDLP using an ion trap quantum computer with improved quantum circuits for the extended Shor’s algorithm. We give precise quantum circuits for extended Shor’s algorithm to calculate discrete logarithms on elliptic curves over prime fields, including modular subtraction, three different modular multiplication, and modular inverse. Additionally, we incorporate and improve upon windowed arithmetic in the circuits to reduce the CNOT-counts. Whereas previous studies mostly focused on minimizing the number of qubits or the depth of the circuit, we focus on minimizing the number of CNOT gates in the circuit, which greatly affects the running time of the algorithm on an ion trap quantum computer. Specifically, we begin by presenting implementations of basic arithmetic operations with the lowest known CNOT-counts, along with improved constructions for modular inverse, point addition, and windowed arithmetic. Next, we precisely estimate that, to execute the extended Shor’s algorithm with the improved circuits to factor an n-bit integer, the CNOT-count required is $$1237n^3/\log n+2n^2+n$$ 1237 n 3 / log n + 2 n 2 + n . Finally, we analyze the running time and feasibility of the extended Shor’s algorithm on an ion trap quantum computer.

arXiv:2305.11410•Cybersecurity•Dec 6, 2023•6 citations

Analysis of RSA and Shor’s algorithm for cryptography: A quantum perspective

Seema Kute, Chitra G. Desai, Mukti E. Jadhav

The complexity of public key algorithms like RSA and variants of Elgamal is based on the involvement of exponentiation in encryption and decryption. RSA is based on integer factorization and variants of Elgamal or based on discrete logarithms and are formed as hard problems. To achieve the perceived level of security, the required key length for public key cryptosystem needs to be determined. Quantum computers are capable of conducting an exponential number of simultaneous computations because of which they can find factors in polynomial time. Shor’s algorithm is popular algorithm for factoring huge integers in polynomial time on quantum computers. This paper presents RSA algorithm followed by various possible attacks for factoring and demonstrates Shor’s algorithm for factoring and discuss results for interpretations.

AIP conference proceedings•Jan 1, 2024•5 citations

Practical Challenges in Executing Shor's Algorithm on Existing Quantum Platforms

Paul Bagourd, Julian Jang-Jaccard, Vincent Lenders +3 more

Quantum computers pose a fundamental threat to widely deployed public-key cryptosystems, such as RSA and ECC, by enabling efficient integer factorization using Shor's algorithm. Theoretical resource estimates suggest that 2048-bit RSA keys could be broken using Shor's algorithm with fewer than a million noisy qubits. Although such machines do not yet exist, the availability of smaller, cloud-accessible quantum processors and open-source implementations of Shor's algorithm raises the question of what key sizes can realistically be factored with today's platforms. In this work, we experimentally investigate Shor's algorithm on several cloud-based quantum computers using publicly available implementations. Our results reveal a substantial gap between the capabilities of current quantum hardware and the requirements for factoring cryptographically relevant integers. In particular, we observe that circuit constructions still need to be highly specific for each modulus, and that machine fidelities are unstable, with high and fluctuating error rates.

quant-pharXiv:2512.15330•Dec 18, 2025•0 citations

Exploring Shor's Algorithm in Cracking RSA Encryption

Aashutosh Srivastava

The present study explores the groundbreaking possibilities of Shor's algorithm in cracking RSA encryption, hence enhancing the security consequences of this extensively employed cryptographic protocol. Due to Shor's algorithm's exponential speed advantage over classical algorithms, RSA encryption—a popular public key cryptosystem—is vulnerable to quantum attacks. To keep its security, RSA depends on the difficulty of factoring huge semi-primes. RSA's security presumptions are called into question by Shor's algorithm's quick factorization on a quantum computer, which has prompted research into post-quantum cryptography solutions to guarantee secure communication in the quantum age. Even with parallel computation, the speed and storage capacity of classical computing are constrained. A key idea in quantum computing is quantum parallelism, which allows quantum systems to carry out several computations at once. In contrast to classical portions. The scope of this paper is to understand the fundamentals of Quantum Computing, the current state of Shor’s algorithm implementation, and efficiency, particularly its application in compromising public key cryptosystems like RSA. The project aims to achieve how factorization is done through classical methods and further, how is this done through Shor’s algorithm and QFT techniques.

International Journal of Sciences: Basic and Applied Research•Nov 15, 2024•0 citations

Simulation of Modular Exponentiation Circuit for Shor's Algorithm in Qiskit

Harashta Tatimma Larasati, Howon Kim

This paper discusses and demonstrates the construction of a quantum modular exponentiation circuit in the Qiskit simulator for use in Shor's Algorithm for integer factorization problem (IFP), which is deemed to be able to crack RSA cryptosystems when a large-qubit quantum computer exists. We base our implementation on Vedral, Barenco, and Ekert (VBE) proposal of quantum modular exponentiation, one of the firsts to explicitly provide the aforementioned circuit. Furthermore, we present an example simulation of how to construct a 7xmod 15 circuit in a step-by-step manner, giving clear and detailed information and consideration that currently not provided in the existing literature, and present the whole circuit for use in Shor's Algorithm. Our present simulation shows that the 4-bit VBE quantum modular exponentiation circuit can be constructed, simulated, and measured in Qiskit, while the Shor's Algorithm incorporating this VBE approach itself can be constructed but not yet simulated due to an overly large number of QASM instructions.

International Conference on Telecommunication Systems, Services, and Applications•Nov 4, 2020•5 citations

Experimental Analysis of Attacks on RSA & Rabin Cryptosystems using Quantum Shor’s Algorithm

Ritu Thombre, Babita Jajodia

In this world of massive communication networks, data security and confidentiality are of crucial importance for maintaining secured private communication and protecting information against eavesdropping attacks. Existing cryptosystems provide data security and confidentiality by the use of encryption and signature algorithms for secured communication. Classical computers use cryptographic algorithms that use the product of two large prime numbers for generating public and private keys. These classical algorithms are based on the fact that integer factorization is a non-deterministic polynomial-time (NP) problem and requires super-polynomial time making it impossible for large enough integers. Shor’s algorithm is a well-known algorithm for factoring large integers in polynomial time and takes only O(b3) time and O(b) space on b-bit number inputs. Shor’s algorithm poses a potential threat to the current security system with the ongoing advancements of Quantum computers. This paper discusses how Shor’s algorithm will be able to break integer factorization-based cryptographic algorithms, for example, Rivest–Shamir–Adleman (RSA) and Rabin Algorithms. As a proof of concept, experimental analysis of Quantum Shor’s algorithm on existing public-key cryptosystems using IBM Quantum Experience is performed for factorizing integers of moderate length (seven bits) due to limitations of thirty-two qubits in present IBM quantum computers. In a nutshell, this work will demonstrate how Shor’s algorithm poses threat to confidentiality and authentication services.

AIJR Proceedings•Jan 1, 2021•7 citations
Since the RSA public key cryptosystem was proposed, it has been widely used because of its strong security. Although the proposal of the Shor’s algorithm offers hope for cracking RSA, it is debatable whether the algorithm can actually pose a threat in practice. From the perspective of the quantum circuit of the Shor’s algorithm, we analyse the feasibility of cracking RSA with improved quantum circuits using an ion-trap quantum computer. We present an improved quantum circuit for the modular exponentiation of a constant, which is the most expensive operation in Shor’s algorithm for integer factorization. Whereas previous studies mostly focused on minimizing the number of qubits or the depth of the circuit, we minimize the number of CNOTs, which greatly affects the time to run the algorithm on an ion-trap quantum computer. First, we give the implementation of the basic arithmetic with the lowest known number of CNOTs and the construction of an improved modular exponentiation of a constant by accumulating intermediate data and using a windowing technique. Then, we precisely estimate the number of improved quantum circuits needed to perform the Shor’s algorithm for factoring an n -bit integer, which is 217 n 3 / log 2 n + 4 n 2 + n . We analyse the running time and feasibility of the Shor’s algorithm on an ion-trap quantum computer according to the number of CNOTs. Finally, we discussed the lower bound of the number of CNOTs needed to implement the Shor’s algorithm.
Abstract The elliptic curve discrete logarithm problem (ECDLP) is a popular choice for cryptosystems due to its high level of security. However, with the advent of the extended Shor’s algorithm, there is concern that ECDLP may soon be vulnerable. While the algorithm does offer hope in solving ECDLP, it is still uncertain whether it can pose a real threat in practice. From the perspective of the quantum circuits of the algorithm, this paper analyzes the feasibility of cracking ECDLP using an ion trap quantum computer with improved quantum circuits for the extended Shor’s algorithm. We give precise quantum circuits for extended Shor’s algorithm to calculate discrete logarithms on elliptic curves over prime fields, including modular subtraction, three different modular multiplication, and modular inverse. Additionally, we incorporate and improve upon windowed arithmetic in the circuits to reduce the CNOT-counts. Whereas previous studies mostly focused on minimizing the number of qubits or the depth of the circuit, we focus on minimizing the number of CNOT gates in the circuit, which greatly affects the running time of the algorithm on an ion trap quantum computer. Specifically, we begin by presenting implementations of basic arithmetic operations with the lowest known CNOT-counts, along with improved constructions for modular inverse, point addition, and windowed arithmetic. Next, we precisely estimate that, to execute the extended Shor’s algorithm with the improved circuits to factor an n-bit integer, the CNOT-count required is 1237n3/log⁡n+2n2+n1237n^3/\log n+2n^2+n1237n3/logn+2n2+n 1237 n 3 / log n + 2 n 2 + n . Finally, we analyze the running time and feasibility of the extended Shor’s algorithm on an ion trap quantum computer.
The complexity of public key algorithms like RSA and variants of Elgamal is based on the involvement of exponentiation in encryption and decryption. RSA is based on integer factorization and variants of Elgamal or based on discrete logarithms and are formed as hard problems. To achieve the perceived level of security, the required key length for public key cryptosystem needs to be determined. Quantum computers are capable of conducting an exponential number of simultaneous computations because of which they can find factors in polynomial time. Shor’s algorithm is popular algorithm for factoring huge integers in polynomial time on quantum computers. This paper presents RSA algorithm followed by various possible attacks for factoring and demonstrates Shor’s algorithm for factoring and discuss results for interpretations.
Quantum computers pose a fundamental threat to widely deployed public-key cryptosystems, such as RSA and ECC, by enabling efficient integer factorization using Shor's algorithm. Theoretical resource estimates suggest that 2048-bit RSA keys could be broken using Shor's algorithm with fewer than a million noisy qubits. Although such machines do not yet exist, the availability of smaller, cloud-accessible quantum processors and open-source implementations of Shor's algorithm raises the question of what key sizes can realistically be factored with today's platforms. In this work, we experimentally investigate Shor's algorithm on several cloud-based quantum computers using publicly available implementations. Our results reveal a substantial gap between the capabilities of current quantum hardware and the requirements for factoring cryptographically relevant integers. In particular, we observe that circuit constructions still need to be highly specific for each modulus, and that machine fidelities are unstable, with high and fluctuating error rates.
The present study explores the groundbreaking possibilities of Shor's algorithm in cracking RSA encryption, hence enhancing the security consequences of this extensively employed cryptographic protocol. Due to Shor's algorithm's exponential speed advantage over classical algorithms, RSA encryption—a popular public key cryptosystem—is vulnerable to quantum attacks. To keep its security, RSA depends on the difficulty of factoring huge semi-primes. RSA's security presumptions are called into question by Shor's algorithm's quick factorization on a quantum computer, which has prompted research into post-quantum cryptography solutions to guarantee secure communication in the quantum age. Even with parallel computation, the speed and storage capacity of classical computing are constrained. A key idea in quantum computing is quantum parallelism, which allows quantum systems to carry out several computations at once. In contrast to classical portions. The scope of this paper is to understand the fundamentals of Quantum Computing, the current state of Shor’s algorithm implementation, and efficiency, particularly its application in compromising public key cryptosystems like RSA. The project aims to achieve how factorization is done through classical methods and further, how is this done through Shor’s algorithm and QFT techniques.
This paper discusses and demonstrates the construction of a quantum modular exponentiation circuit in the Qiskit simulator for use in Shor's Algorithm for integer factorization problem (IFP), which is deemed to be able to crack RSA cryptosystems when a large-qubit quantum computer exists. We base our implementation on Vedral, Barenco, and Ekert (VBE) proposal of quantum modular exponentiation, one of the firsts to explicitly provide the aforementioned circuit. Furthermore, we present an example simulation of how to construct a 7xmod 15 circuit in a step-by-step manner, giving clear and detailed information and consideration that currently not provided in the existing literature, and present the whole circuit for use in Shor's Algorithm. Our present simulation shows that the 4-bit VBE quantum modular exponentiation circuit can be constructed, simulated, and measured in Qiskit, while the Shor's Algorithm incorporating this VBE approach itself can be constructed but not yet simulated due to an overly large number of QASM instructions.
In this world of massive communication networks, data security and confidentiality are of crucial importance for maintaining secured private communication and protecting information against eavesdropping attacks. Existing cryptosystems provide data security and confidentiality by the use of encryption and signature algorithms for secured communication. Classical computers use cryptographic algorithms that use the product of two large prime numbers for generating public and private keys. These classical algorithms are based on the fact that integer factorization is a non-deterministic polynomial-time (NP) problem and requires super-polynomial time making it impossible for large enough integers. Shor’s algorithm is a well-known algorithm for factoring large integers in polynomial time and takes only O(b3) time and O(b) space on b-bit number inputs. Shor’s algorithm poses a potential threat to the current security system with the ongoing advancements of Quantum computers. This paper discusses how Shor’s algorithm will be able to break integer factorization-based cryptographic algorithms, for example, Rivest–Shamir–Adleman (RSA) and Rabin Algorithms. As a proof of concept, experimental analysis of Quantum Shor’s algorithm on existing public-key cryptosystems using IBM Quantum Experience is performed for factorizing integers of moderate length (seven bits) due to limitations of thirty-two qubits in present IBM quantum computers. In a nutshell, this work will demonstrate how Shor’s algorithm poses threat to confidentiality and authentication services.