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

IEEE International Conference on Quantum Computing and Engineering (QCE)

Quantum Resource Estimation of Arithmetic Primitives

Ethan R. Hansen, Sanskriti Joshi, Hannah Rarick

Published Sep 17, 2023• 0 citations
Publisher

Abstract

A major component of RSA cryptanalsysis, factoring a number that is a product of two large primes is computationally intensive. Using Shor's algorithm, there is a possibility of the factorization taking a fraction of the time on a quantum computer. To implement this level of algorithm, an analysis of the resources required would help with understanding the requirements for the hardware based on the software implementation and vice versa.

DOI
10.1109/qce57702.2023.10290

Related papers

Pitfalls of the Sublinear QAOA-Based Factorization Algorithm

Sergey V. Grebnev, Maxim A. Gavreev, Evgeniy O. Kiktenko +3 more

Quantum computing devices are believed to be powerful in solving the prime factorization problem, which is at the heart of widely deployed public-key cryptographic tools. However, the implementation of Shor’s quantum factorization algorithm requires significant resources scaling linearly with the number size; taking into account an overhead that is required for quantum error correction the estimation is that 20 millions of (noisy) physical qubits are required for factoring 2048-bit RSA key in 8 hours. Recent proposal by Yan et. al. claims a possibility of solving the factorization problem with sublinear quantum resources. As we demonstrate in our work, this proposal lacks systematic analysis of the computational complexity of the classical part of the algorithm, which exploits the Schnorr’s lattice-based approach. We provide several examples illustrating the need in additional resource analysis for the proposed quantum factorization algorithm.

arXiv:2303.04656•IEEE Access•Jan 1, 2023•4 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

RSA Encryption and the Shor Factoring Algorithm

Alice Flarend, Bob Hilborn

Abstract This chapter is the most formidable in the book, but it provides a deep and complete understanding of the classic Shor factoring algorithm. Alice and Bob set the context for the algorithm by explaining how the difficulty of factoring large numbers plays a critical role in securing encrypted communications channels, using RSA encryption as an example. The Shor algorithm, if implemented on a sufficiently large quantum computer, could defeat those encryption schemes by finding those factors relatively quickly, a task that would take years or more on even the fastest classical supercomputers. Alice and Bob lead us through some number theory to establish the connection between factoring and finding the period of a periodic function. They then show how the clever use of quantum algorithms—this is Shor’s main contribution—leads to a fast way to find the required period using quantum Fourier transforms.

•Apr 15, 2022•0 citations

Performance Analysis of Shor's Algorithm for Integer Factorization Using Quantum and Classical Approaches

T. Thamaraimanalan, Bhupendra Singh, M. Mohankumar +1 more

Factoring large numbers poses a significant chal-lenge in contemporary cryptography and security practices. Shor's algorithm presents a remarkable advancement over clas- sical methods by providing exponential acceleration in factoring large numbers, presenting a possible risk to traditional cryptography methods. The algorithm relies on the Quantum Fourier Transform (QFT) and modular exponentiation principles to efficiently ascertain the period (x) of a given large number (N). Upon determining the period using classical methods, the prime factors of the large number can be easily computed. To eval- uate the algorithm's efficiency and scalability, both simulation- based experiments and theoretical analyses are conducted. The algorithm is simulated utilizing the Qiskit back end to estimate resources, including Clifford gates, T gates, T depth, Full depth, and qubits, across a range of large numbers.

International Conference on Advanced Computing and Communication Systems (ICACCS)•Mar 14, 2024•9 citations

Implementation and Analysis of Shor's Algorithm to Break RSA Cryptosystem Security

Siyon Singh, Eric Sakk

The ongoing development of Quantum Computing (QC) is a breakthrough paradigm that holds the power to revolutionize the way we process information and solve complex problems today. Quantum Computation works on the fundamental principles of Superposition and Entanglement, enabling Quantum Computers to Leverage the power of Physics in Computing. QC has the potential to revolutionize fields such as Drug Development, Financial Modeling, Optimization, and Cryptography. Shor’s algorithm, a quantum algorithm used to factorize large numbers, poses significant threats to RSA, a widely used public key cryptosystem. RSA relies on the difficulty of factoring large semi-primes to keep its security. Shor's algorithm's ability to factorize quickly on a quantum computer undermines RSA's security assumptions, necessitating the exploration of post-quantum cryptographic solutions to ensure secure communication in the quantum era. The goal of this paper is to assess the present state of Shor's algorithm implementation and efficiency, specifically its application in the context of compromising public key cryptosystems like RSA.

•Dec 14, 2023•1 citation

Implementation and Analysis of Shor's Algorithm to Break RSA Cryptosystem Security

Siyon Singh, Eric Sakk

The ongoing development of Quantum Computing (QC) is a breakthrough paradigm that holds the power to revolutionize the way we process information and solve complex problems today. Quantum Computation works on the fundamental principles of Superposition and Entanglement, enabling Quantum Computers to Leverage the power of Physics in Computing. QC has the potential to revolutionize fields such as Drug Development, Financial Modeling, Optimization, and Cryptography. Shor’s algorithm, a quantum algorithm used to factorize large numbers, poses significant threats to RSA, a widely used public key cryptosystem. RSA relies on the difficulty of factoring large semi-primes to keep its security. Shor's algorithm's ability to factorize quickly on a quantum computer undermines RSA's security assumptions, necessitating the exploration of post-quantum cryptographic solutions to ensure secure communication in the quantum era. The goal of this paper is to assess the present state of Shor's algorithm implementation and efficiency, specifically its application in the context of compromising public key cryptosystems like RSA.

•Jan 8, 2024•11 citations
A major component of RSA cryptanalsysis, factoring a number that is a product of two large primes is computationally intensive. Using Shor's algorithm, there is a possibility of the factorization taking a fraction of the time on a quantum computer. To implement this level of algorithm, an analysis of the resources required would help with understanding the requirements for the hardware based on the software implementation and vice versa.
Quantum computing devices are believed to be powerful in solving the prime factorization problem, which is at the heart of widely deployed public-key cryptographic tools. However, the implementation of Shor’s quantum factorization algorithm requires significant resources scaling linearly with the number size; taking into account an overhead that is required for quantum error correction the estimation is that 20 millions of (noisy) physical qubits are required for factoring 2048-bit RSA key in 8 hours. Recent proposal by Yan et. al. claims a possibility of solving the factorization problem with sublinear quantum resources. As we demonstrate in our work, this proposal lacks systematic analysis of the computational complexity of the classical part of the algorithm, which exploits the Schnorr’s lattice-based approach. We provide several examples illustrating the need in additional resource analysis for the proposed quantum factorization algorithm.
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.
Abstract This chapter is the most formidable in the book, but it provides a deep and complete understanding of the classic Shor factoring algorithm. Alice and Bob set the context for the algorithm by explaining how the difficulty of factoring large numbers plays a critical role in securing encrypted communications channels, using RSA encryption as an example. The Shor algorithm, if implemented on a sufficiently large quantum computer, could defeat those encryption schemes by finding those factors relatively quickly, a task that would take years or more on even the fastest classical supercomputers. Alice and Bob lead us through some number theory to establish the connection between factoring and finding the period of a periodic function. They then show how the clever use of quantum algorithms—this is Shor’s main contribution—leads to a fast way to find the required period using quantum Fourier transforms.
Factoring large numbers poses a significant chal-lenge in contemporary cryptography and security practices. Shor's algorithm presents a remarkable advancement over clas- sical methods by providing exponential acceleration in factoring large numbers, presenting a possible risk to traditional cryptography methods. The algorithm relies on the Quantum Fourier Transform (QFT) and modular exponentiation principles to efficiently ascertain the period (x) of a given large number (N). Upon determining the period using classical methods, the prime factors of the large number can be easily computed. To eval- uate the algorithm's efficiency and scalability, both simulation- based experiments and theoretical analyses are conducted. The algorithm is simulated utilizing the Qiskit back end to estimate resources, including Clifford gates, T gates, T depth, Full depth, and qubits, across a range of large numbers.
The ongoing development of Quantum Computing (QC) is a breakthrough paradigm that holds the power to revolutionize the way we process information and solve complex problems today. Quantum Computation works on the fundamental principles of Superposition and Entanglement, enabling Quantum Computers to Leverage the power of Physics in Computing. QC has the potential to revolutionize fields such as Drug Development, Financial Modeling, Optimization, and Cryptography. Shor’s algorithm, a quantum algorithm used to factorize large numbers, poses significant threats to RSA, a widely used public key cryptosystem. RSA relies on the difficulty of factoring large semi-primes to keep its security. Shor's algorithm's ability to factorize quickly on a quantum computer undermines RSA's security assumptions, necessitating the exploration of post-quantum cryptographic solutions to ensure secure communication in the quantum era. The goal of this paper is to assess the present state of Shor's algorithm implementation and efficiency, specifically its application in the context of compromising public key cryptosystems like RSA.
The ongoing development of Quantum Computing (QC) is a breakthrough paradigm that holds the power to revolutionize the way we process information and solve complex problems today. Quantum Computation works on the fundamental principles of Superposition and Entanglement, enabling Quantum Computers to Leverage the power of Physics in Computing. QC has the potential to revolutionize fields such as Drug Development, Financial Modeling, Optimization, and Cryptography. Shor’s algorithm, a quantum algorithm used to factorize large numbers, poses significant threats to RSA, a widely used public key cryptosystem. RSA relies on the difficulty of factoring large semi-primes to keep its security. Shor's algorithm's ability to factorize quickly on a quantum computer undermines RSA's security assumptions, necessitating the exploration of post-quantum cryptographic solutions to ensure secure communication in the quantum era. The goal of this paper is to assess the present state of Shor's algorithm implementation and efficiency, specifically its application in the context of compromising public key cryptosystems like RSA.