A distributed Shor’s algorithm is used to factorize a semiprime with two quantum computers using quantum teleportation to transport quantum states of qubits in parallel. We propose another distributed Shor’s algorithm with sequential quantum teleportation to improve the existing one. It explores how to employ distributed quantum computing through a quantum entanglement pair of qubits to transport quantum states of qubits sequentially. We combined two quantum computers to perform the quantum phase estimation (QPE) of Shor’s algorithm. This reduced the required number of qubits for a single quantum computer, decreased quantum circuit depth, mitigated the impact of insufficient decoherence time, and accelerated the process of breaking cryptographic systems such as Rivest-Shamir-Adleman (RSA). The designed quantum circuit was executed on the IBM Quantum Lab platform to verify its correctness. We analyzed and compared the required numbers of qubits to run different versions of Shor’s algorithm for individual quantum computers, as well as the numbers of qubits required to break different RSA cryptographic systems.
A distributed Shor’s algorithm is used to factorize a semiprime with two quantum computers using quantum teleportation to transport quantum states of qubits in parallel. We propose another distributed Shor’s algorithm with sequential quantum teleportation to improve the existing one. It explores how to employ distributed quantum computing through a quantum entanglement pair of qubits to transport quantum states of qubits sequentially. We combined two quantum computers to perform the quantum phase estimation (QPE) of Shor’s algorithm. This reduced the required number of qubits for a single quantum computer, decreased quantum circuit depth, mitigated the impact of insufficient decoherence time, and accelerated the process of breaking cryptographic systems such as Rivest-Shamir-Adleman (RSA). The designed quantum circuit was executed on the IBM Quantum Lab platform to verify its correctness. We analyzed and compared the required numbers of qubits to run different versions of Shor’s algorithm for individual quantum computers, as well as the numbers of qubits required to break different RSA cryptographic systems.
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.
Shor's algorithm is one of the most significant quantum algorithms. Shor's algorithm can factor large integers with a certain success probability in polynomial time. However, Shor's algorithm requires an unbearable amount of qubits in the NISQ (Noisy Intermediate-scale Quantum) era. To reduce the resources required for Shor's algorithm, in this paper we first propose a new distributed phase estimation algorithm. Our distributed phase estimation algorithm does not require quantum communication and it reduces the number of qubits of a single node compared to the traditional phase estimation algorithm (non-iterative version). Then we apply our distributed phase estimation algorithm to form a distributed order-finding algorithm for Shor's algorithm. Compared with the traditional Shor's algorithm (non-iterative version), the maximum number of qubits required by a single node of our dristributed order-finding algorithm is reduced by (2−k2)L−log2k−O(1) when factoring an L-bit integer (k is the number of compute nodes). The communication complexity of our distributed order-finding algorithm is O(kL).
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.
Quantum computing has raised significant concerns regarding the security of classical cryptographic systems, particularly RSA, as it depends on the computational difficulty of factoring large semiprime numbers.In this study, we demonstrate the practical application of Shor's algorithm by successfully factorizing a semiprime integer, up to 30 bits (857830637 = 29167 X 29411) using the QuantumRings simulator.Our work highlights the effectiveness of Shor's algorithm in solving the factorization problem in polynomial time, which will significantly improve over the classical method for a large number.The results suggest that with advances in quantum hardware, such as increasing qubit counts and improving error correction, breaking larger RSA keys (e.g., RSA-2048) may soon become feasible.This seriously threatens current cryptographic systems, emphasizing the need to adopt post-quantum cryptography.Our findings aim to raise awareness among researchers, policymakers, and industry leaders of the importance of preparing for a quantum-safe future.
Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.
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.