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

Panhellenic Conference on Informatics

Implementation of Shor's Algorithm and Reliability of Quantum Computing Devices

Maria E. Sabani, Ilias Galanis, Ilias Κ. Savvas, Georgia Garani

Published Nov 26, 2021• 6 citations
Publisher

Abstract

The process to find the prime factors of a large number, the “factoring problem” is believed to be a very hard problem. For this reason, it is the cornerstone of modern cryptographic schemes, like RSA cryptosystem. In 1994, Professor Peter Shor proposed a new polynomial-time quantum algorithm that finds the prime factors of a number with many digits. This was a bolt from the blue for the security of transactions and electronic communications and became an example of how quantum computing changes our perception of security and safety. In this paper Shor's Algorithm is presented and an implementation, a way to factor number 21 is described. In addition, some reliability issues of quantum devices were considered in order to explore the potentiality of Shor's algorithm.

DOI
10.1145/3503823.3503895

Related papers

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

Fundamental Structure of Shor’s Quantum Algorithm for Factoring Integers

Turgut Hanoymak, Akram Chehrazi

One of the most well known mathematically hard problems in number theory is the integer factorization problem, roughly stated that decomposition of a composite number into its prime factors. In modern cryptography, RSA encryption algorithm whose security is based on integer factorization problem is highly practical, widespread and up to date no classical algorithm having polynomial running time for the factorization of large numbers is known. In 1994, Peter Shor proposed an efficient algorithm on quantum computer. In this paper, we  mention about the fundamentals of  Shor's quantum algorithm illustrating a concrete example.

Turkish Journal of Mathematics and Computer Science•Dec 31, 2019•0 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 of 5-Qubit approach-based Shor's Algorithm in IBM Qiskit

G. R. Mounica, G. Manimaran, Lauret Jerome +1 more

RSA cryptography is a principle part in today's cyber-security frameworks, which intensely depends on the diffi-culty of factorizing large integers. Finding a factor of large prime number is not a small feature compared to the time complexity for computation on a classical computer is far beyond comprehension. Back in 1994, Peter Shor proposed a quantum algorithm to factorize integers much more efficiently than a classical computer. This can effectively break asymmetric cryptosystems such as RSA or Diffie-Hellman, depicted as the most famous quantum algorithm. It leverages the efficacy proclaimed by quantum bits and clearly shows how quantum computers can outperform classical ones in specific tasks. In this paper, we show how Shor's algorithm factorizes an integer into its two prime factors. Shor uses both classical and quantum computation to perform this task in polynomial time, using Euclidean algorithm and find the greatest common divisor (gcd) of two numbers in the classical part. Thereafter, the power of Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE) is utilised for period-finding using quantum bits. We have implemented this algorithm on IBM's Quantum Lab and successfully factorized the number 15 into its prime factors as 5 and 3, by using 5 qubits. This paper provides an overview of the implementation of Shor's algorithm involving QPE, QFT, Modular Exponentiation and the corresponding individual implementations, the only prerequisite being, to know how a qubit works.

IEEE Pune Section International Conference (PuneCon)•Dec 16, 2021•17 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

RSA Prime Factorization on IBM Qiskit

Matthew Evans Audric Rengkung, Arya Wicaksana

The advancement of quantum computing in recent years poses severe threats to the RSA public-key cryptosystem. The RSA cryptosystem fundamentally relies its security on the computational hardness of number theory problems: prime factorization (integer factoring). Shor’s quantum factoring algorithm could theoretically answer the computational problem in polynomial time. This paper contributes to the experiment and demonstration of Shor’s quantum factoring algorithm for RSA prime factorization using IBM Qiskit. The performance of the quantum program is evaluated based on user time and the success probability. The results show that a more significant public modulus N in the RSA public key improves factorization’s computational hardness, requiring more quantum bits to solve. A further enhancement on implementing Shor’s oracle function is essential in increasing success probability and reducing the number of shots required.

Journal of Internet Services and Information Security•May 30, 2023•8 citations
The process to find the prime factors of a large number, the “factoring problem” is believed to be a very hard problem. For this reason, it is the cornerstone of modern cryptographic schemes, like RSA cryptosystem. In 1994, Professor Peter Shor proposed a new polynomial-time quantum algorithm that finds the prime factors of a number with many digits. This was a bolt from the blue for the security of transactions and electronic communications and became an example of how quantum computing changes our perception of security and safety. In this paper Shor's Algorithm is presented and an implementation, a way to factor number 21 is described. In addition, some reliability issues of quantum devices were considered in order to explore the potentiality of Shor's algorithm.
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.
One of the most well known mathematically hard problems in number theory is the integer factorization problem, roughly stated that decomposition of a composite number into its prime factors. In modern cryptography, RSA encryption algorithm whose security is based on integer factorization problem is highly practical, widespread and up to date no classical algorithm having polynomial running time for the factorization of large numbers is known. In 1994, Peter Shor proposed an efficient algorithm on quantum computer. In this paper, we  mention about the fundamentals of  Shor's quantum algorithm illustrating a concrete example.
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.
RSA cryptography is a principle part in today's cyber-security frameworks, which intensely depends on the diffi-culty of factorizing large integers. Finding a factor of large prime number is not a small feature compared to the time complexity for computation on a classical computer is far beyond comprehension. Back in 1994, Peter Shor proposed a quantum algorithm to factorize integers much more efficiently than a classical computer. This can effectively break asymmetric cryptosystems such as RSA or Diffie-Hellman, depicted as the most famous quantum algorithm. It leverages the efficacy proclaimed by quantum bits and clearly shows how quantum computers can outperform classical ones in specific tasks. In this paper, we show how Shor's algorithm factorizes an integer into its two prime factors. Shor uses both classical and quantum computation to perform this task in polynomial time, using Euclidean algorithm and find the greatest common divisor (gcd) of two numbers in the classical part. Thereafter, the power of Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE) is utilised for period-finding using quantum bits. We have implemented this algorithm on IBM's Quantum Lab and successfully factorized the number 15 into its prime factors as 5 and 3, by using 5 qubits. This paper provides an overview of the implementation of Shor's algorithm involving QPE, QFT, Modular Exponentiation and the corresponding individual implementations, the only prerequisite being, to know how a qubit works.
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.
The advancement of quantum computing in recent years poses severe threats to the RSA public-key cryptosystem. The RSA cryptosystem fundamentally relies its security on the computational hardness of number theory problems: prime factorization (integer factoring). Shor’s quantum factoring algorithm could theoretically answer the computational problem in polynomial time. This paper contributes to the experiment and demonstration of Shor’s quantum factoring algorithm for RSA prime factorization using IBM Qiskit. The performance of the quantum program is evaluated based on user time and the success probability. The results show that a more significant public modulus N in the RSA public key improves factorization’s computational hardness, requiring more quantum bits to solve. A further enhancement on implementing Shor’s oracle function is essential in increasing success probability and reducing the number of shots required.