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

Successful Shor's Factorization of N=1031167 using the IBM Quantum Systems

Jiří Tomčala

Published Dec 3, 2025• 0 citations
Publisher

Abstract

So far, the highest number factorized on a quantum computer using Shor’s algorithm was 35. This poster shows that much larger numbers can be factorized using this algorithm on current quantum computers. The factorization of number 1031167, along with the quantum circuits used and results from the IBM quantum systems ibm_brisbane and ibm_kyoto, is shown. Shor’s algorithm was proposed in 1994, but only now has quantum technology evolved to such a level that its realization has become possible. The bottleneck of this algorithm is the implementation of the modular exponentiation function (MEF), which is also the subject of this poster. Thanks to the appropriately chosen parameter "a", this implementation was quite simple. Therefore, it was not a problem to use the Qiskit framework to program and run the necessary quantum circuits on the IBM quantum systems. The measured results of the whole circuit were then accurate enough to determine both factors. Since they were correct, it can be stated that the highest number factorized by a quantum computer using Shor's algorithm is now 1031167.

DOI
10.5281/zenodo.17806923

Related papers

Circuit implementation of Shor's algorithm for the factorization of small integers in Qiskit

Iheb Eddine Gharbi, Amor Gueddana, Hichem Eleuch +1 more

To factor an integer N into a product of two other numbers N1 and N2, Shor’s algorithm uses the Quantum Fourier Transform on n qubits, denoted QFTn, to determine the period r of a Modular Exponentiation Function (MEF), which is later used to compute a factor of N. In this work, we present Shor’s algorithm for factoring an integer of n qubits and illustrate an example with n=4. We implement our algorithm using Qiskit and IBM quantum computers, which also can be adapted on other quantum computing platforms with minor adjustments. We discuss the IBM quantum computer limitations for running our circuit and show the impact of device imperfections on the factored result.

Quantum Communications and Quantum Imaging•Aug 13, 2024•3 citations

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•18 citations

Quantum Integer Factorization by 3 Different Methods, Their Implementations and Results

Jiří Tomčala

The content of this poster is a description of the implementation of two well-known quantum integer factorization methods and, in addition, a proposal of a new, third way along with some examples of its use. For all three methods, the measured results of their circuits will be shown.The first method is Shor's algorithm, where a quantum circuit is used only to find the period of a specially assembled modular exponentiating function. The rest of the algorithm is preprocessing and postprocessing that can be done on a classical computer, so one could say that this is a hybrid algorithm. New results of the successful factorization of the number 119, performed by this algorithm on a real 7-qubit quantum computer, will be presented. It is worth mentioning here that the highest number successfully factorized by this algorithm on a real quantum computer so far was 35.The second method is variational quantum factorization (VQF). In this method, preprocessing builds a system of equations based on the classical binary multiplication procedure of two numbers, resulting in a factorized number. This system of equations is then used to form a Hamiltonian in such a way that its ground state corresponds to the solution of this equation system. Only now the hybrid quantum optimization comes into play to iteratively find this ground state. The advantage over Shor's algorithm is that this method does not require a fault-tolerant quantum computer, but on the other hand it approaches the solution iteratively using a classical computer, which reduces the potential quantum advantage.The new, third method employs Grover's search algorithm in an unusual way to create a quantum factorization circuit. A key part of this approach is the quantum implementation of a multiplying oracle. The main advantage of this method over the previous ones is that it can be used to assemble a relatively simple universal factorization circuit. Moreover, there is almost no preprocessing and postprocessing required. This method is still under development, but this poster will present the first results.

•Dec 18, 2025•0 citations

Enhanced Security Algorithm for Integer Factorization in Quantum Computing: Optimizing Shor’s Algorithm

Rashmi Kuksal, Sumit Chaudhary, Ashish Bhatt

With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.

International Conference on Innovative Mechanisms for Industry Applications•Oct 1, 2026•0 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•10 citations

On the Various Ways of Quantum Implementation of the Modular Exponentiation Function for Shor’s Factorization

Jiří Tomčala

Abstract The content of this paper is a detailed analysis of possible ways how to quantum implement a key part of Shor’s factorization algorithm, the modular exponentiation function. This implementation is a bottleneck for performing quantum factorization with polynomial complexity, which would make it possible to factorize really large numbers in a reasonable amount of time. In this paper, not only the general theory is presented, but also the results of successful factorizations of the numbers 247 and 143 using Shor’s algorithm from a quantum computer simulator. An interesting fact is that no ancillary qubits were needed in these factorizations. Based on the content of the paper, the conclusion also suggests possible future work on the development of this modular exponentiation function implementation.

International Journal of Theoretical Physics•Jan 10, 2024•8 citations
So far, the highest number factorized on a quantum computer using Shor’s algorithm was 35. This poster shows that much larger numbers can be factorized using this algorithm on current quantum computers. The factorization of number 1031167, along with the quantum circuits used and results from the IBM quantum systems ibm_brisbane and ibm_kyoto, is shown. Shor’s algorithm was proposed in 1994, but only now has quantum technology evolved to such a level that its realization has become possible. The bottleneck of this algorithm is the implementation of the modular exponentiation function (MEF), which is also the subject of this poster. Thanks to the appropriately chosen parameter "a", this implementation was quite simple. Therefore, it was not a problem to use the Qiskit framework to program and run the necessary quantum circuits on the IBM quantum systems. The measured results of the whole circuit were then accurate enough to determine both factors. Since they were correct, it can be stated that the highest number factorized by a quantum computer using Shor's algorithm is now 1031167.
To factor an integer N into a product of two other numbers N1 and N2, Shor’s algorithm uses the Quantum Fourier Transform on n qubits, denoted QFTn, to determine the period r of a Modular Exponentiation Function (MEF), which is later used to compute a factor of N. In this work, we present Shor’s algorithm for factoring an integer of n qubits and illustrate an example with n=4. We implement our algorithm using Qiskit and IBM quantum computers, which also can be adapted on other quantum computing platforms with minor adjustments. We discuss the IBM quantum computer limitations for running our circuit and show the impact of device imperfections on the factored result.
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.
The content of this poster is a description of the implementation of two well-known quantum integer factorization methods and, in addition, a proposal of a new, third way along with some examples of its use. For all three methods, the measured results of their circuits will be shown.The first method is Shor's algorithm, where a quantum circuit is used only to find the period of a specially assembled modular exponentiating function. The rest of the algorithm is preprocessing and postprocessing that can be done on a classical computer, so one could say that this is a hybrid algorithm. New results of the successful factorization of the number 119, performed by this algorithm on a real 7-qubit quantum computer, will be presented. It is worth mentioning here that the highest number successfully factorized by this algorithm on a real quantum computer so far was 35.The second method is variational quantum factorization (VQF). In this method, preprocessing builds a system of equations based on the classical binary multiplication procedure of two numbers, resulting in a factorized number. This system of equations is then used to form a Hamiltonian in such a way that its ground state corresponds to the solution of this equation system. Only now the hybrid quantum optimization comes into play to iteratively find this ground state. The advantage over Shor's algorithm is that this method does not require a fault-tolerant quantum computer, but on the other hand it approaches the solution iteratively using a classical computer, which reduces the potential quantum advantage.The new, third method employs Grover's search algorithm in an unusual way to create a quantum factorization circuit. A key part of this approach is the quantum implementation of a multiplying oracle. The main advantage of this method over the previous ones is that it can be used to assemble a relatively simple universal factorization circuit. Moreover, there is almost no preprocessing and postprocessing required. This method is still under development, but this poster will present the first results.
With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.
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.
Abstract The content of this paper is a detailed analysis of possible ways how to quantum implement a key part of Shor’s factorization algorithm, the modular exponentiation function. This implementation is a bottleneck for performing quantum factorization with polynomial complexity, which would make it possible to factorize really large numbers in a reasonable amount of time. In this paper, not only the general theory is presented, but also the results of successful factorizations of the numbers 247 and 143 using Shor’s algorithm from a quantum computer simulator. An interesting fact is that no ancillary qubits were needed in these factorizations. Based on the content of the paper, the conclusion also suggests possible future work on the development of this modular exponentiation function implementation.