Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

E3S Web of Conferences

Speed improvement of the quantum factorization algorithm of P. Shor by upgrade its classical part

Larissa V. Cherckesova, Olga Alexandrovna Safaryan, Разумов Павел Владимирович, Irina A. Pilipenko, Yu. I. Ivanov, Ivan Smirnov

Published Jan 1, 2020• 1 citation
Publisher

Abstract

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%.

DOI
10.1051/e3sconf/202022401016

Related papers

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

Implementation of Shor’s Quantum Factoring Algorithm Using ProjectQ Framework

Adjie Wahyu Wicaksono, Arya Wicaksana

Prime number factorization is a problem in computer science where the solution to that problem takes super-polynomial time classically. Shor’s quantum factoring algorithm is able to solve the problem in polynomial time by harnessing the power of quantum computing. The implementation of the quantum algorithm itself is not detailed by Shor in his paper. In this paper, an approach and experiment to implement Shor’s quantum factoring algorithm are proposed. The implementation is done using Python and a quantum computer simulator from ProjectQ. The testing and evaluation are completed in two computers with different hardware specifications. User time of the implementation is measured in comparison with other quantum computer simulators: ProjectQ and Quantum Computing Playground. This comparison was done to show the performance of Shor’s algorithm when simulated using different hardware. There is a 33% improvement in the execution time (user time) between the two computers with the accuracy of prime factorization in this implementation is inversely proportional to the number of qubits used. Further improvements upon the program that has been developed for this paper is its accuracy in terms of finding the factors of a number and the number of qubits used, as previously mentioned.

International Journal of Engineering and Advanced Technology•Nov 22, 2019•4 citations

How Quantum Computing Breaks RSA? - A Study of Shor's Algorithm

Arnav Jain

The advent of quantum computing poses a fundamental threat to classical cryptographic systems, particularly RSA encryption, which relies on the computational limit of prime factorization. This paper presents a comparative analysis of four integer factorization approaches-a selfcurated brute-force classical implementation, optimized Trial Division, Pollard's Rho algorithm, and Shor's algorithmevaluated across a dataset of increasing semiprime inputs representative of scaled-down RSA encryption keys. Through Python-based implementations and simulations, we empirically measure and plot runtime complexity for classical methods while modeling theoretical runtimes for Shor's algorithm, given hardware limitations. Our findings reveal the exponential scaling limitations of classical algorithms, and contrast them with the polynomial-time behavior of Shor's algorithm. Despite being simulated, Shor's consistently flatter runtime trendline demonstrated its theoretical superiority and the critical urgency of post-quantum cryptography. This study not only visualizes the performance divide between classical and quantum paradigms but also underscores the transformational potential of quantum computing in modern cryptanalysis.

IEEE MIT Undergraduate Research Technology Conference (URTC)•Oct 10, 2025•0 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

CAPACITIVE COMPLEXITY OF DETERMINING GCD IN THE SHOR S ALGORITHM

Valerii Hlukhov

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.

ELECTRICAL AND COMPUTER SYSTEMS•Nov 30, 2020•0 citations

A quantum algorithm for greatest common divisor problem

Wen Wang, Xu Jiang, Liangzhu Mu +1 more

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.

arXiv:1707.06430•Jul 20, 2017•2 citations
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.
Prime number factorization is a problem in computer science where the solution to that problem takes super-polynomial time classically. Shor’s quantum factoring algorithm is able to solve the problem in polynomial time by harnessing the power of quantum computing. The implementation of the quantum algorithm itself is not detailed by Shor in his paper. In this paper, an approach and experiment to implement Shor’s quantum factoring algorithm are proposed. The implementation is done using Python and a quantum computer simulator from ProjectQ. The testing and evaluation are completed in two computers with different hardware specifications. User time of the implementation is measured in comparison with other quantum computer simulators: ProjectQ and Quantum Computing Playground. This comparison was done to show the performance of Shor’s algorithm when simulated using different hardware. There is a 33% improvement in the execution time (user time) between the two computers with the accuracy of prime factorization in this implementation is inversely proportional to the number of qubits used. Further improvements upon the program that has been developed for this paper is its accuracy in terms of finding the factors of a number and the number of qubits used, as previously mentioned.
The advent of quantum computing poses a fundamental threat to classical cryptographic systems, particularly RSA encryption, which relies on the computational limit of prime factorization. This paper presents a comparative analysis of four integer factorization approaches-a selfcurated brute-force classical implementation, optimized Trial Division, Pollard's Rho algorithm, and Shor's algorithmevaluated across a dataset of increasing semiprime inputs representative of scaled-down RSA encryption keys. Through Python-based implementations and simulations, we empirically measure and plot runtime complexity for classical methods while modeling theoretical runtimes for Shor's algorithm, given hardware limitations. Our findings reveal the exponential scaling limitations of classical algorithms, and contrast them with the polynomial-time behavior of Shor's algorithm. Despite being simulated, Shor's consistently flatter runtime trendline demonstrated its theoretical superiority and the critical urgency of post-quantum cryptography. This study not only visualizes the performance divide between classical and quantum paradigms but also underscores the transformational potential of quantum computing in modern cryptanalysis.
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 to2n2^{n}2nbits.
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.
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.