The article analyzes the results of finding the period r of the function y = axmodM (a is a random number) which is used in the Shor's factorization algorithm for quantum computers. The module M is the product of two primes p and q. The article analyzes the solutions r obtained for various a, for which the capacitive complexity H of finding the greatest common divisor GCD(ar/2 + 1, M) is the least. A digital quantum computer is a classic processor and its digital quantum coprocessor. A digital quantum coprocessor with hundreds and thousands of digital qubits can be implemented in one programmable logic integrated circuit FPGA. In the Shor’s algorithm, the factorization problem of the number M reduces to the problem of determining the period r of the function y. It is known that GCD(ar/2 + 1, M) can be a divisor of the number M The task of the quantum coprocessor in implementing the Shor’s algorithm is to find the period r. After that it is necessary to find the GCD. Since for random a the problem of finding the period r has many solutions, these solutions can be compared by the value of one of the arguments when finding the GCD - the number ar / 2 . In this case, H = (rlog2a)/2 is taken for analysis. It approximately represents the bit depth of binary codes that a classic computer will have to process when determining the GCD. H can vary over a wide range from tens to thousands of bits even for small values of M. In this research the period r, which ensures the least complexity of the subsequent task of finding the GCD, is most often a solution for a = 3 and a = 2, but it can also occur often with other values of a. To clarify the revealed patterns, especially for large M, it is necessary to conduct additional research.
The article analyzes the results of finding the period r of the function y = axmodM (a is a random number) which is used in the Shor's factorization algorithm for quantum computers. The module M is the product of two primes p and q. The article analyzes the solutions r obtained for various a, for which the capacitive complexity H of finding the greatest common divisor GCD(ar/2 + 1, M) is the least. A digital quantum computer is a classic processor and its digital quantum coprocessor. A digital quantum coprocessor with hundreds and thousands of digital qubits can be implemented in one programmable logic integrated circuit FPGA. In the Shor’s algorithm, the factorization problem of the number M reduces to the problem of determining the period r of the function y. It is known that GCD(ar/2 + 1, M) can be a divisor of the number M The task of the quantum coprocessor in implementing the Shor’s algorithm is to find the period r. After that it is necessary to find the GCD. Since for random a the problem of finding the period r has many solutions, these solutions can be compared by the value of one of the arguments when finding the GCD - the number ar / 2 . In this case, H = (rlog2a)/2 is taken for analysis. It approximately represents the bit depth of binary codes that a classic computer will have to process when determining the GCD. H can vary over a wide range from tens to thousands of bits even for small values of M. In this research the period r, which ensures the least complexity of the subsequent task of finding the GCD, is most often a solution for a = 3 and a = 2, but it can also occur often with other values of a. To clarify the revealed patterns, especially for large M, it is necessary to conduct additional research.
This report discusses Shor’s quantum factorization algorithm and ρ–Pollard’s factorization algorithm. Shor’s quantum factorization algorithm consists of classical and quantum parts. In the classical part, it is proposed to use Euclidean algorithm, to find the greatest common divisor (GCD), but now exist large number of modern algorithms for finding GCD. Results of calculations of 8 algorithms were considered, among which algorithm with lowest execution rate of task was identified, which allowed the quantum algorithm as whole to work faster, which in turn provides greater potential for practical application of Shor’s quantum algorithm. Standard quantum Shor’s algorithm was upgraded by replacing the binary algorithm with iterative shift algorithm, canceling random number generation operation, using additive chain algorithm for raising to power. Both Shor’s algorithms (standard and upgraded) are distinguished by their high performance, which proves much faster and insignificant increase in time in implementation of data processing. In addition, it was possible to modernize Shor’s quantum algorithm in such way that its efficiency turned out to be higher than standard algorithm because classical part received an improvement, which allows an increase in speed by 12%.
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.
We present a quantum algorithm solving the greatest common divisor (GCD) problem. This quantum algorithm possesses similar computational complexity with classical algorithms, such as the well-known Euclidean algorithm for GCD. This algorithm is an application of the quantum algorithms for the hidden subgroup problems, the same as Shor factoring algorithm. Explicit quantum circuits realized by quantum gates for this quantum algorithm are provided. We also give a computer simulation of this quantum algorithm and present the expected outcomes for the corresponding quantum circuit.
Shor’s algorithm is a well-known probabilistic method for factoring large composite integers in polynomial-time on a quantum computer. The method computes the order r of a random element x in the group Z∗N and uses that information for splitting N with an application of the greatest common divisor algorithm. However, being probabilistic, the success of Shor’s algorithm relies on some special properties of N. If r is even and xr/2 £ -1 mod N, then gcd(xr/2 - 1, N) reveals a nontrivial factor of N and the method succeeds. But even assuming that r is even and being given the complete prime factorization of N it is not obvious whether xr/2 £ -1 mod N and, therefore, it is not easy to assert whether Shor’s algorithm would split N without running it and looking at its answer. We present a strategy for detecting whether the splitting occurs without any need for running the quantum order-finding algorithm, but we must be given the prime factorization of N. This has allowed us to produce the first direct evidence of the probability of success of Shor’s method. The composites chosen were the product of two randomly-generated probable primes of similar sizes that pass the Miller-Rabin test.
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.
Quantum computing is inherently abstract and often counterintuitive from the perspective of classical physics. For learners to develop a deeper understanding, it is useful to study a practical example thoroughly, from its mathematical formalism to quantum circuit implementation. Shor's algorithm for period finding, which can then be used for prime factorization, is demonstrated in this paper due to its practical significance. While numerous publications on Shor's algorithm exist, they tend to focus on advanced theoretical analysis, specific implementation details, or narrowly defined research aspects; consequently, they are often not well-suited for educational purposes for beginning and intermediate learners. This paper presents a rigorous step-by-step walkthrough of Shor's algorithm, utilizing the conventional approach, and discusses the construction of the quantum oracle with illustrative numerical examples. This is followed by classical simulations and implementations on actual quantum hardware. The aim is to allow learners with minimal mathematical background to follow and understand the algorithm. Through this process, the paper also attempts to interpret and connect the key underlying quantum computing concepts of superposition, entanglement, interference, quantum oracle, and phase kick-back that are often assumed to be trivial and omitted in research papers, yet are particularly challenging for novice learners to internalize. In the numerical examples, reduced-qubit cases are included. By contrasting the results from the reduced-qubit configurations with the standard ones, learners can better appreciate the key enablers in Shor's algorithm and how the accuracy decreases with a smaller number of qubits. Moreover, reduced-qubit examples (e.g., 5 qubits) are small enough to be implemented in a hardware emulator, such as a low-cost and low-capacity Field Programmable Gate Array (FPGA), which can be used in experimental hardware classes for students to understand how to use an FPGA to simulate quantum circuits.