© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1805.10478

Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer

Avinash Dash, Deepankar Sarmah, Bikash K. Behera, Prasanta Kumar Panigrahi

Published May 26, 2018• 23 citations

Abstract

Factoring large integers using a quantum computer is an outstanding research problem that can illustrate true quantum advantage over classical computers. Exponential time order is required in order to find the prime factors of an integer by means of classical computation. However, the order can be drastically reduced by converting the factorization problem to an optimization one and solving it using a quantum computer. Recent works involving both theoretical and experimental approaches use Shor's algorithm, adiabatic quantum computation and quantum annealing principles to factorize integers. However, our work makes use of the generalized Grover's algorithm as proposed by Liu, with an optimal version of classical algorithm/analytic algebra. We utilize the phase-matching property of the above algorithm for only amplitude amplification purposes to avoid an inherent phase factor that prevents perfect implementation of the algorithm. Here we experimentally demonstrate the factorization of two bi-primes, 4088459 and 966887 using IBM's 5- and 16-qubit quantum processors, hence making those the largest numbers that have been factorized on a quantum device. Using the above 5-qubit processor, we also realize the factorization of a tri-prime integer 175, which had not been achieved to date. We observe good agreement between experimental and theoretical results with high fidelities. The difficulty of the factorization experiments has been analyzed and it has been concluded that the solution to this problem depends on the level of simplification chosen, not the size of the number factored. In principle, our results can be extended to factorize any multi-prime integer with minimum quantum resources.

DOI: 10.48550/arxiv.1805.10478

Related papers

Factorization of large tetra and penta prime numbers on IBM quantum processor

Ritu Dhaulakhandi, Bikash K. Behera, Felix J. Seo

The factorization of large digit integers in polynomial time is a challenging computational task to decipher. The development of Shor’s algorithm sparked a new resolution for solving the factorization problem. However, putting Shor’s algorithm into use in real-world situations presents major difficulties. The algorithm largely depends on the availability of large-scale, fault-tolerant quantum computers, which are not available at present. The need for qubit coherence and error correction makes the algorithm susceptible to noise and decoherence, hindering its practical realization. Therefore, exploring alternative quantum factorization algorithms and investing in quantum computing hardware advancements are vital steps toward overcoming these drawbacks and harnessing the full potential of quantum computing for factorization tasks. This article explores an alternative method of converting the factorization problem into an optimization problem using appropriate analytic algebra. The generalized Grover’s protocol is used to increase the amplitude of the necessary states and, in turn, help in the execution of the quantum factorization of tetra and penta primes as a proof of concept for different integers, including 875, 1 269 636 549 803, and 4375, using three and four qubits of IBMQ Perth (a seven-qubit processor). The fidelity of the quantum factorization protocol with the IBMQ Perth qubits was near unity. A generalization of the method is provided at the end for implementing factorization problems in various cases.

arXiv:2304.04999•APL Quantum•Jun 1, 2024•6 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•17 citations

Factoring semi-primes with (quantum) SAT-solvers

Michele Mosca, Sebastian R. Verschoor

The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor's quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor's algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware.

arXiv:1902.01448•Scientific Reports•May 14, 2022•17 citations

Quantum Shor's Algorithm vs. Classical General Number Field Sieve (GNFS) Approach for Large Integer Factorization

S. S. Kavitha, Narasimha Kaulgud, B. Sharmila +3 more

Quantum integer factorization is a groundbreaking field that explores the use of quantum algorithms, notably Shor's algorithm, to efficiently factorize large integers into their prime components. Its potential implications on modern encryption techniques, such as the Rivest-Shamir-Adleman (RSA) algorithm, are of considerable interest. This paper's central aim is to contrast the computational time and implementation of the Integer Factorization Problem (IFP) between classical and quantum computers. The inner workings of Quantum Shor's algorithm are broken down step by step, and the estimated processing time is contrasted with the classical General Number Field Sieve (GNFS) approach. Given the exponential speedup provided by quantum computing, this comparison helps assess Shor's algorithm's possible advantage over GNFS in factoring large numbers. Direct comparisons with GNFS are currently difficult due to Shor's algorithm's reliance on large-scale quantum computer development for practical execution speeds. This paper focuses on solving integer factorization up to$2^{n}$bits.

International Conference on Next Generation Communication & Information Processing (INCIP)•Jan 23, 2025•1 citation

Experimental prime factorization via the feedback quantum control

K. B. Hari Krishnan, Vishal Varma, T. S. Mahesh

Prime factorization on quantum processors is typically implemented either via circuit-based approaches such as Shor's algorithm or through Hamiltonian optimization methods based on adiabatic, annealing, or variational techniques. While Shor's algorithm demands high-fidelity quantum gates, Hamiltonian optimization schemes, with prime factors encoded as degenerate ground states of a problem Hamiltonian, generally require substantial classical post-processing to determine control parameters. We propose an all-quantum, measurement-based feedback approach that iteratively steers a quantum system toward the target ground state, eliminating the need for classical computation of drive parameters once the problem Hamiltonian is determined and realized. As a proof of principle, we experimentally factor the biprime 551 using a three-qubit NMR quantum register and numerically analyze the robustness of the method against control field-errors. We further demonstrate scalability by numerically implementing the FALQON factorization of larger biprimes, 9,167 and 2,106,287, using 5 and 9 qubits, respectively.

quant-pharXiv:2601.16116•Jan 23, 2026•0 citations

Prime factorization using quantum annealing and computational algebraic geometry

Raouf Dridi, Hedayat Alghassi

We investigate prime factorization from two perspectives: quantum annealing and computational algebraic geometry, specifically Gröbner bases. We present a novel autonomous algorithm which combines the two approaches and leads to the factorization of all bi-primes up to just over 200000, the largest number factored to date using a quantum processor. We also explain how Gröbner bases can be used to reduce the degree of Hamiltonians.

arXiv:1604.05796•Scientific Reports•Feb 21, 2017•76 citations

Factoring large integers using a quantum computer is an outstanding research problem that can illustrate true quantum advantage over classical computers. Exponential time order is required in order to find the prime factors of an integer by means of classical computation. However, the order can be drastically reduced by converting the factorization problem to an optimization one and solving it using a quantum computer. Recent works involving both theoretical and experimental approaches use Shor's algorithm, adiabatic quantum computation and quantum annealing principles to factorize integers. However, our work makes use of the generalized Grover's algorithm as proposed by Liu, with an optimal version of classical algorithm/analytic algebra. We utilize the phase-matching property of the above algorithm for only amplitude amplification purposes to avoid an inherent phase factor that prevents perfect implementation of the algorithm. Here we experimentally demonstrate the factorization of two bi-primes, 4088459 and 966887 using IBM's 5- and 16-qubit quantum processors, hence making those the largest numbers that have been factorized on a quantum device. Using the above 5-qubit processor, we also realize the factorization of a tri-prime integer 175, which had not been achieved to date. We observe good agreement between experimental and theoretical results with high fidelities. The difficulty of the factorization experiments has been analyzed and it has been concluded that the solution to this problem depends on the level of simplification chosen, not the size of the number factored. In principle, our results can be extended to factorize any multi-prime integer with minimum quantum resources.

The factorization of large digit integers in polynomial time is a challenging computational task to decipher. The development of Shor’s algorithm sparked a new resolution for solving the factorization problem. However, putting Shor’s algorithm into use in real-world situations presents major difficulties. The algorithm largely depends on the availability of large-scale, fault-tolerant quantum computers, which are not available at present. The need for qubit coherence and error correction makes the algorithm susceptible to noise and decoherence, hindering its practical realization. Therefore, exploring alternative quantum factorization algorithms and investing in quantum computing hardware advancements are vital steps toward overcoming these drawbacks and harnessing the full potential of quantum computing for factorization tasks. This article explores an alternative method of converting the factorization problem into an optimization problem using appropriate analytic algebra. The generalized Grover’s protocol is used to increase the amplitude of the necessary states and, in turn, help in the execution of the quantum factorization of tetra and penta primes as a proof of concept for different integers, including 875, 1 269 636 549 803, and 4375, using three and four qubits of IBMQ Perth (a seven-qubit processor). The fidelity of the quantum factorization protocol with the IBMQ Perth qubits was near unity. A generalization of the method is provided at the end for implementing factorization problems in various cases.

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 computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor's quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor's algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware.

Quantum integer factorization is a groundbreaking field that explores the use of quantum algorithms, notably Shor's algorithm, to efficiently factorize large integers into their prime components. Its potential implications on modern encryption techniques, such as the Rivest-Shamir-Adleman (RSA) algorithm, are of considerable interest. This paper's central aim is to contrast the computational time and implementation of the Integer Factorization Problem (IFP) between classical and quantum computers. The inner workings of Quantum Shor's algorithm are broken down step by step, and the estimated processing time is contrasted with the classical General Number Field Sieve (GNFS) approach. Given the exponential speedup provided by quantum computing, this comparison helps assess Shor's algorithm's possible advantage over GNFS in factoring large numbers. Direct comparisons with GNFS are currently difficult due to Shor's algorithm's reliance on large-scale quantum computer development for practical execution speeds. This paper focuses on solving integer factorization up to

2^{n}

bits.

Prime factorization on quantum processors is typically implemented either via circuit-based approaches such as Shor's algorithm or through Hamiltonian optimization methods based on adiabatic, annealing, or variational techniques. While Shor's algorithm demands high-fidelity quantum gates, Hamiltonian optimization schemes, with prime factors encoded as degenerate ground states of a problem Hamiltonian, generally require substantial classical post-processing to determine control parameters. We propose an all-quantum, measurement-based feedback approach that iteratively steers a quantum system toward the target ground state, eliminating the need for classical computation of drive parameters once the problem Hamiltonian is determined and realized. As a proof of principle, we experimentally factor the biprime 551 using a three-qubit NMR quantum register and numerically analyze the robustness of the method against control field-errors. We further demonstrate scalability by numerically implementing the FALQON factorization of larger biprimes, 9,167 and 2,106,287, using 5 and 9 qubits, respectively.