In this paper, an attempt is made to apply the Euler's Totient function and Euler's theorem to organizing calculations of the period of the modular exponentiation function inspired by Shor's quantum algorithm. A particular method for determining the period by a classical computer is described and a general method for its determination is proposed. For the first 10,000 prime numbers, semiprime numbers are compiled and the distribution of periods of exponentiation functions modulo a semiprime number is studied. The relationship between the Euler's Totient function and the period of the modular exponentiation function is established.
In this paper, an attempt is made to apply the Euler's Totient function and Euler's theorem to organizing calculations of the period of the modular exponentiation function inspired by Shor's quantum algorithm. A particular method for determining the period by a classical computer is described and a general method for its determination is proposed. For the first 10,000 prime numbers, semiprime numbers are compiled and the distribution of periods of exponentiation functions modulo a semiprime number is studied. The relationship between the Euler's Totient function and the period of the modular exponentiation function is established.
We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.
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.
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.
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 constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to N=557993 with up to n=39 qubits, we confirm earlier, smaller-n results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-n implementations of quantum computers.