Shor's algorithm is a significant quantum algorithm for factoring a number N. The key technique of the Shor's algo- rithm is turning the factoring problem into the problem of finding the period of a function. Based on the key technique and the monotony of the mode function, an approach how to determine the period of a function is introduced. Mean- while an important parameter selection for period-finding is optimized. Several experiments discussed imply that the approach and the parameter selection are both rigorous.
Shor's algorithm is a significant quantum algorithm for factoring a number N. The key technique of the Shor's algo- rithm is turning the factoring problem into the problem of finding the period of a function. Based on the key technique and the monotony of the mode function, an approach how to determine the period of a function is introduced. Mean- while an important parameter selection for period-finding is optimized. Several experiments discussed imply that the approach and the parameter selection are both rigorous.
A fundamental problem in factorization by Shor's algorithm [1] is the implementation of the modular exponentiation function. The period of this function is important for determining the individual factors, so its accurate implementation is for successful factorization critical.The imprecision of current quantum computers requires that any quantum circuits should be as simple as possible. Both in terms of the number of qubits used, the number of quantum gates and the depth of the quantum circuit. Therefore, it is necessary to search for an optimal variant for the implementation of the above-mentioned modular exponentiation function.The standard method is to implement individual arithmetic functions [2] which can be combined to achieve the desired modular exponentiation function. This process, however, creates a very complex quantum circuit, so that its measured result (probability distribution) will be so skewed that it will not be possible to reliably obtain the period of sought.Another way is to create a special quantum circuit for one particular modular exponentiation function [3]. Such a circuit is of course simpler than the circuit created by the above universal implementation, but in practice it only makes sense for testing the functionality of the surrounding quantum circuit for period detection.A very interesting possibility for the implementation of arithmetic functions is to use the direct and inverse quantum Fourier transform [4]. For a quantum computer, these transformations are very easy operations, and this interesting feature can then be used to advantage in these various implementations.This contribution will explore these possible approaches and show their advantages and disadvantages through concrete examples.
Factoring large numbers poses a significant chal-lenge in contemporary cryptography and security practices. Shor's algorithm presents a remarkable advancement over clas- sical methods by providing exponential acceleration in factoring large numbers, presenting a possible risk to traditional cryptography methods. The algorithm relies on the Quantum Fourier Transform (QFT) and modular exponentiation principles to efficiently ascertain the period (x) of a given large number (N). Upon determining the period using classical methods, the prime factors of the large number can be easily computed. To eval- uate the algorithm's efficiency and scalability, both simulation- based experiments and theoretical analyses are conducted. The algorithm is simulated utilizing the Qiskit back end to estimate resources, including Clifford gates, T gates, T depth, Full depth, and qubits, across a range of large numbers.
Quantum computing has emerged as an important interdisciplinary field, merging theories in mathematics, physics and computer science. So far, a significant portion of research in quantum computing has focused on the design of quantum algorithms. Quantum Com-puters requires very different algorithms for factorization, which plays an important role in the field of quantum computing and shor’s algo-rithm is used to address integer factorization problem. Shor's algorithm is important because it breaks a widely used public-key cryptography scheme known as RSA. This paper discusses the refinement of quantum factorization algorithm. Keywords: - quantum algorithm, factorization, gcd, prime decomposition, shor’s algorithm.
The intent of this thesis is to elucidate the quantum computing algorithm developed by Peter Shor called Shor's algorithm. We will provide a detailed description and simulation of the algorithm using MATLAB. Precursory information regarding quantum phenomena such as superposition, entanglement, and Dirac notation, will be described in great detail so that the reader may have a better understanding of the operations in Shor's algorithm. Quantum computers store and transport information quite differently than their classical counterparts. We will provide a quick overview of these differences to high- light the benefit of utilizing quantum phenomena in a computer in order to create massive parallel computations. Thus, reducing the complexity time for classical algorithms used to solve problems such as the prime factorization problem and the period finding problem. The Quantum Fourier Transform is a principle component in Shor's algorithm. We will explicitly define the Quantum Fourier Transform and show that it is a unitary transformation. We will also show how the Quantum Fourier Transform, as well as another unitary transformation called the Hadamard transform, functions in Shor's algorithm. One of the initial parameters in Shor's algorithm is to select a random variable. We will examine the erratic effects of this random variable as well as how it effects the probability of us successfully reducing an integer into a product of two primes. We will provide a thorough analysis of the randomness in Shor's algorithm. We will also show how measuring the state of our quantum system as well as selecting a suitable random variable impacts finding the period of the Quantum Fourier Transform which in turn will either give a high or low probability of obtaining a factor of some integer.
This paper explores a quantum-inspired technique for factoring semi-prime integers, a problem central to the security of RSA cryptography. While Shor's algorithm offers a polynomial-time solution on a quantum computer, posing a significant threat to RSA, current quantum hardware limitations hinder its practical implementation. This study simulates Shor's algorithm classically, replacing the quantum period-finding subroutine—the source of the quantum speedup—with a classical method to analyze its performance. The experiments factored semi-primes ranging from 2 to 8 digits, demonstrating that while the technique works, the execution time increases exponentially with the size of the number, escalating from seconds for small integers to an order of minutes for an 8-digit number. This highlights the inefficiency of classical period-finding compared to the quantum approach. The results validate the theoretical framework of Shor's algorithm but underscore the impracticality of classical simulations for cryptographic-scale integers. This work also explores the necessity of advancing quantum computing to realize scalable factorization while classical methods remain confined to pedagogical or small-scale applications. The study emphasizes the urgency of hybrid quantum-classical optimizations and reinforces Shor's algorithm as pivotal for future cryptographic vulnerability assessments and quantum-ready solutions.
Quantum machine learning is the combination of quantum computing and classical machine learning. It helps in solving the problems of one field to another field. Shor’s algorithm is used for factoring the integers in polynomial time. Since the bestknown classical algorithm requires super polynomial time to factor the product of two primes, the widely used cryptosystem, RSA, relies on factoring being impossible for large enough integers. In this paper we will focus on the quantum part of Shor’s algorithm, which actually solves the problem of period finding. In polynomial time factoring problem can be turned into a period finding problem so an efficient period finding algorithm can be used to factor integers efficiently.