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

International Conference on IT Innovation and Knowledge Discovery (ITIKD)

Using Single Time of Quantum Computer for Shor's Factoring Algorithm

Yousef Alhammadi

Published Mar 8, 2023• 0 citations
Publisher

Abstract

Peter Shor's in 1994 developed a factoring algorithm that can factor a composite number$\boldsymbol{n}$in a polynomial time by using a quantum computer in one step of the algorithm. The algorithm may contain a loop that requires calling a quantum computer many times to find the order of selected number$a, a\in Z_{n}$. In this paper, the improvement to the Shor's factoring algorithm guarantees the single use of the quantum computer to find the order, where the rest of the algorithm can be implemented by a classical computer. A numerical example for the original and improved version is presented.

DOI
10.1109/itikd56332.2023.10099702

Related papers

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

Maria E. Sabani, Ilias Galanis, Ilias Κ. Savvas +1 more

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.

Panhellenic Conference on Informatics•Nov 26, 2021•6 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 of Shor’s Quantum Factoring Algorithm Using ProjectQ Framework

Adjie Wahyu Wicaksono, Arya Wicaksana

Prime number factorization is a problem in computer science where the solution to that problem takes super-polynomial time classically. Shor’s quantum factoring algorithm is able to solve the problem in polynomial time by harnessing the power of quantum computing. The implementation of the quantum algorithm itself is not detailed by Shor in his paper. In this paper, an approach and experiment to implement Shor’s quantum factoring algorithm are proposed. The implementation is done using Python and a quantum computer simulator from ProjectQ. The testing and evaluation are completed in two computers with different hardware specifications. User time of the implementation is measured in comparison with other quantum computer simulators: ProjectQ and Quantum Computing Playground. This comparison was done to show the performance of Shor’s algorithm when simulated using different hardware. There is a 33% improvement in the execution time (user time) between the two computers with the accuracy of prime factorization in this implementation is inversely proportional to the number of qubits used. Further improvements upon the program that has been developed for this paper is its accuracy in terms of finding the factors of a number and the number of qubits used, as previously mentioned.

International Journal of Engineering and Advanced Technology•Nov 22, 2019•4 citations

Shor's factorization algorithm

E. Desurvire

This chapter describes what is generally considered to be one of the most important and historical contributions to the field of quantum computing, namely Shor's factorization algorithm . As its name indicates, this algorithm makes it possible to factorize numbers, which consists in their decomposition into a unique product of prime numbers. Other classical factorization algorithms previously developed have a complexity or computing time that increases exponentially with the number size, making the task intractable if not hopeless for large numbers. In contrast, Shor's algorithm is able to factor a number of any size in polynomial time , making the factorization problem tractable should a quantum computer ever be realized in the future. Since Shor's algorithm is based on several nonintuitive properties and other mathematical subtleties, this chapter presents a certain level of difficulty. With the previous chapters and tools readily assimilated, and some patience in going through the different preliminary steps required, such a difficulty is, however, quite surmountable. I have sought to make this description of Shor's algorithm as mathematically complete as possible and crack-free, while avoiding some academic considerations that may not be deemed necessary from any engineering perspective. Eventually, Shor's algorithm is described in only a few basic instructions. What is conceptually challenging is to grasp why it works so well, and also to feel comfortable with the fact that its implementation actually takes a fair amount of trial and error. The two preliminaries of Shor's algorithm are the phase estimation and the related order-finding algorithms.

Cambridge University Press eBooks•Feb 19, 2009•0 citations

Distributed Shor's algorithm

Ligang Xiao, Daowen Qiu, Le Luo +1 more

Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm, the quantum part of which is to estimate $s/r$, where $r$ is the ``order" and $s$ is some natural number that less than $r$. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of $s/r$.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly $L/2$ qubits for factoring an $L$-bit integer and reduces the circuit depth of each computer.

arXiv:2207.05976•Quantum Information and Computation•Jan 1, 2023•24 citations

Experimental Implementation of Shor's Quantum Algorithm to Break RSA

Aminah Albuainain, Jana Alansari, Samiyah Alrashidi +3 more

Nowadays, quantum computing is an important topic since it allows computations to be completed in a small amount of the time. The goal of using quantum computers (QC) is to solve an increasing number of problems that were previously intractable to address with traditional computing. The classical approaches work with bits, which are made up of 0s and 1s, whereas QC uses qubits. Classical computing is limited by storage capacity and speed of calculations, even when parallel computation is conducted on it. Compared to traditional methods, quantum parallelism allows the storage to be reduced exponentially with the potential of a shorter amount of time. Besides, Peter Shor's algorithm can solve the factorization problem used in RSA in polynomial time, whereas in a classical computer, factoring any big integer is intractable. The purpose of this research is to explore and implement quantum computing schemes and how Shor's algorithm can break RSA algorithms.

International Conference on Computational Intelligence and Communication Networks (CICN)•Dec 4, 2022•12 citations
Peter Shor's in 1994 developed a factoring algorithm that can factor a composite numbern\boldsymbol{n}nin a polynomial time by using a quantum computer in one step of the algorithm. The algorithm may contain a loop that requires calling a quantum computer many times to find the order of selected numbera,a∈Zna, a\in Z_{n}a,a∈Zn​. In this paper, the improvement to the Shor's factoring algorithm guarantees the single use of the quantum computer to find the order, where the rest of the algorithm can be implemented by a classical computer. A numerical example for the original and improved version is presented.
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.
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.
Prime number factorization is a problem in computer science where the solution to that problem takes super-polynomial time classically. Shor’s quantum factoring algorithm is able to solve the problem in polynomial time by harnessing the power of quantum computing. The implementation of the quantum algorithm itself is not detailed by Shor in his paper. In this paper, an approach and experiment to implement Shor’s quantum factoring algorithm are proposed. The implementation is done using Python and a quantum computer simulator from ProjectQ. The testing and evaluation are completed in two computers with different hardware specifications. User time of the implementation is measured in comparison with other quantum computer simulators: ProjectQ and Quantum Computing Playground. This comparison was done to show the performance of Shor’s algorithm when simulated using different hardware. There is a 33% improvement in the execution time (user time) between the two computers with the accuracy of prime factorization in this implementation is inversely proportional to the number of qubits used. Further improvements upon the program that has been developed for this paper is its accuracy in terms of finding the factors of a number and the number of qubits used, as previously mentioned.
This chapter describes what is generally considered to be one of the most important and historical contributions to the field of quantum computing, namely Shor's factorization algorithm . As its name indicates, this algorithm makes it possible to factorize numbers, which consists in their decomposition into a unique product of prime numbers. Other classical factorization algorithms previously developed have a complexity or computing time that increases exponentially with the number size, making the task intractable if not hopeless for large numbers. In contrast, Shor's algorithm is able to factor a number of any size in polynomial time , making the factorization problem tractable should a quantum computer ever be realized in the future. Since Shor's algorithm is based on several nonintuitive properties and other mathematical subtleties, this chapter presents a certain level of difficulty. With the previous chapters and tools readily assimilated, and some patience in going through the different preliminary steps required, such a difficulty is, however, quite surmountable. I have sought to make this description of Shor's algorithm as mathematically complete as possible and crack-free, while avoiding some academic considerations that may not be deemed necessary from any engineering perspective. Eventually, Shor's algorithm is described in only a few basic instructions. What is conceptually challenging is to grasp why it works so well, and also to feel comfortable with the fact that its implementation actually takes a fair amount of trial and error. The two preliminaries of Shor's algorithm are the phase estimation and the related order-finding algorithms.
Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm, the quantum part of which is to estimate s/rs/rs/r, where rrr is the ``order" and sss is some natural number that less than rrr. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of s/rs/rs/r.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly L/2L/2L/2 qubits for factoring an LLL-bit integer and reduces the circuit depth of each computer.
Nowadays, quantum computing is an important topic since it allows computations to be completed in a small amount of the time. The goal of using quantum computers (QC) is to solve an increasing number of problems that were previously intractable to address with traditional computing. The classical approaches work with bits, which are made up of 0s and 1s, whereas QC uses qubits. Classical computing is limited by storage capacity and speed of calculations, even when parallel computation is conducted on it. Compared to traditional methods, quantum parallelism allows the storage to be reduced exponentially with the potential of a shorter amount of time. Besides, Peter Shor's algorithm can solve the factorization problem used in RSA in polynomial time, whereas in a classical computer, factoring any big integer is intractable. The purpose of this research is to explore and implement quantum computing schemes and how Shor's algorithm can break RSA algorithms.