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

International Conference on Electrical Engineering and Information Communication Technology

A Compare between Shor's quantum factoring algorithm and General Number Field Sieve

Shah Muhammad Hamdi, Syed Tauhid Zuhori, Firoz Mahmud, Biprodip Pal

Published Apr 1, 2014• 14 citations
Publisher

Abstract

Factoring large integers has been one of the most difficult problems in the history of mathematics and computer science. There was no efficient solution of this problem until Shor's algorithm emerged. Shor's algorithm is a polynomial time factoring algorithm which works on a quantum computer. Quantum computing is a new paradigm of computing that uses quantum mechanical phenomena in solving problems. The computers we are using right now are called classical computer. The most efficient classical factoring algorithm is General Number Field Sieve (GNFS). GNFS also cannot factor integers in polynomial time. In this paper, we compared these two algorithms in factoring integer in a standalone system.

DOI
10.1109/iceeict.2014.6919115

Related papers

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

A Comparative Analysis of Shor’s Algorithm and Factorization Methods

Alaa Khudhair Abbas, Saba Hussein Rashid, Saba Alaa Abdulwahhab +1 more

Large integer factorization has long been a significant problem in computer science and mathematics. With the advent of Shor's algorithm, a polynomial-time factoring technique created for quantum computers, an effective solution to this problem became possible. Using quantum mechanics concepts. Qantum computing appears to be a novel approach to solving these complex problems. Classical computers are currently using the General Number Field Sieve (GNFS), Trial Division, the Elliptic Curve Method (EC),Fermat's Factorization, and the Quadratic Sieve(QS) are some of the best classical factoring techniques. However, this study examines these conventional approaches to determine their implications for cryptographic security, analyzing their weaknesses, usefulness, strengths, and difficulties. This paper alsodiscusses how Shor's algorithm affects cybersecurity because of its exponential speed advantage over traditional techniques. This paper also uses Shor’s algorithm get Q*P in using quantum facilities to break the algorithm like RSA algorithm

Journal of Al-Nahrain University-Science•Jun 15, 2026•0 citations

Quantum Computing Algorithms for Integer Factorization: A Comparative Analysis

Nadia Ahmed

The field of quantum computing has witnessed remarkable advancements in recent years, particularly in its potential applications to solve computationally hard problems such as integer factorization. a comparative analysis of quantum computing algorithms for integer factorization, focusing on their theoretical foundations, computational complexity, and practical implications. We review prominent algorithms such as Shor's algorithm, which leverages quantum parallelism and period finding to efficiently factor large composite integers, and compare them with classical factorization algorithms like the General Number Field Sieve (GNFS). Through a comprehensive examination of algorithmic strategies, runtime complexities, and quantum circuit implementations, we assess the relative strengths and limitations of quantum computing approaches for integer factorization. Furthermore, we discuss potential challenges and future research directions in harnessing the power of quantum computing to address cryptographic security and algorithmic complexity in the era of post-quantum cryptography.

Modern Dynamics: Mathematical Progressions.•May 25, 2024•8 citations

Fundamental Structure of Shor’s Quantum Algorithm for Factoring Integers

Turgut Hanoymak, Akram Chehrazi

One of the most well known mathematically hard problems in number theory is the integer factorization problem, roughly stated that decomposition of a composite number into its prime factors. In modern cryptography, RSA encryption algorithm whose security is based on integer factorization problem is highly practical, widespread and up to date no classical algorithm having polynomial running time for the factorization of large numbers is known. In 1994, Peter Shor proposed an efficient algorithm on quantum computer. In this paper, we  mention about the fundamentals of  Shor's quantum algorithm illustrating a concrete example.

Turkish Journal of Mathematics and Computer Science•Dec 31, 2019•0 citations

Quadratic Sieve Factorization Quantum Algorithm and its Simulation

Amandeep Singh Bhatia, Ajay Kumar

Quantum computing is a winsome field that concerns with the behaviour and nature of energy at the quantum level to improve the efficiency of computations. In recent years, quantum computation is receiving much attention for its capability to solve difficult problems efficiently in contrast to classical computers. Specifically, some well-known public-key cryptosystems depend on the difficulty of factoring large numbers, which takes a very long time. It is expected that the emergence of a quantum computer has the potential to break such cryptosystems by 2020 due to the discovery of powerful quantum algorithms (Shor's factoring, Grover's search algorithm and many more). In this paper, we have designed a quantum variant of the second fastest classical factorization algorithm named "Quadratic Sieve". We have constructed the simulation framework of quantized quadratic sieve algorithm using high-level programming language Mathematica. Further, the simulation results are performed on a classical computer to get a feel of the quantum system and proved that it is more efficient than its classical variants from computational complexity point of view.

arXiv:2005.11668•May 24, 2020•1 citation

Implementation of Shor’s Algorithm in QISKIT by Quantum Computing using IBMQ

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.

International Journal of Advanced Trends in Computer Science and Engineering•Apr 5, 2021•0 citations
Factoring large integers has been one of the most difficult problems in the history of mathematics and computer science. There was no efficient solution of this problem until Shor's algorithm emerged. Shor's algorithm is a polynomial time factoring algorithm which works on a quantum computer. Quantum computing is a new paradigm of computing that uses quantum mechanical phenomena in solving problems. The computers we are using right now are called classical computer. The most efficient classical factoring algorithm is General Number Field Sieve (GNFS). GNFS also cannot factor integers in polynomial time. In this paper, we compared these two algorithms in factoring integer in a standalone system.
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.
Large integer factorization has long been a significant problem in computer science and mathematics. With the advent of Shor's algorithm, a polynomial-time factoring technique created for quantum computers, an effective solution to this problem became possible. Using quantum mechanics concepts. Qantum computing appears to be a novel approach to solving these complex problems. Classical computers are currently using the General Number Field Sieve (GNFS), Trial Division, the Elliptic Curve Method (EC),Fermat's Factorization, and the Quadratic Sieve(QS) are some of the best classical factoring techniques. However, this study examines these conventional approaches to determine their implications for cryptographic security, analyzing their weaknesses, usefulness, strengths, and difficulties. This paper alsodiscusses how Shor's algorithm affects cybersecurity because of its exponential speed advantage over traditional techniques. This paper also uses Shor’s algorithm get Q*P in using quantum facilities to break the algorithm like RSA algorithm
The field of quantum computing has witnessed remarkable advancements in recent years, particularly in its potential applications to solve computationally hard problems such as integer factorization. a comparative analysis of quantum computing algorithms for integer factorization, focusing on their theoretical foundations, computational complexity, and practical implications. We review prominent algorithms such as Shor's algorithm, which leverages quantum parallelism and period finding to efficiently factor large composite integers, and compare them with classical factorization algorithms like the General Number Field Sieve (GNFS). Through a comprehensive examination of algorithmic strategies, runtime complexities, and quantum circuit implementations, we assess the relative strengths and limitations of quantum computing approaches for integer factorization. Furthermore, we discuss potential challenges and future research directions in harnessing the power of quantum computing to address cryptographic security and algorithmic complexity in the era of post-quantum cryptography.
One of the most well known mathematically hard problems in number theory is the integer factorization problem, roughly stated that decomposition of a composite number into its prime factors. In modern cryptography, RSA encryption algorithm whose security is based on integer factorization problem is highly practical, widespread and up to date no classical algorithm having polynomial running time for the factorization of large numbers is known. In 1994, Peter Shor proposed an efficient algorithm on quantum computer. In this paper, we  mention about the fundamentals of  Shor's quantum algorithm illustrating a concrete example.
Quantum computing is a winsome field that concerns with the behaviour and nature of energy at the quantum level to improve the efficiency of computations. In recent years, quantum computation is receiving much attention for its capability to solve difficult problems efficiently in contrast to classical computers. Specifically, some well-known public-key cryptosystems depend on the difficulty of factoring large numbers, which takes a very long time. It is expected that the emergence of a quantum computer has the potential to break such cryptosystems by 2020 due to the discovery of powerful quantum algorithms (Shor's factoring, Grover's search algorithm and many more). In this paper, we have designed a quantum variant of the second fastest classical factorization algorithm named "Quadratic Sieve". We have constructed the simulation framework of quantized quadratic sieve algorithm using high-level programming language Mathematica. Further, the simulation results are performed on a classical computer to get a feel of the quantum system and proved that it is more efficient than its classical variants from computational complexity point of view.
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.