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

arXiv:2005.11668

Quadratic Sieve Factorization Quantum Algorithm and its Simulation

Amandeep Singh Bhatia, Ajay Kumar

Published May 24, 2020• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2005.11668

Related papers

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

Shah Muhammad Hamdi, Syed Tauhid Zuhori, Firoz Mahmud +1 more

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.

International Conference on Electrical Engineering and Information Communication Technology•Apr 1, 2014•14 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

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

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 Solving Complex Mathematical Problems

Et al. Lalit Mohan Trivedi

The power of quantum mechanics, that is too complex for conventional computers, can be solved by an innovative model of computing known as quantum computing. Quantum algorithms can provide exponential speedups for some types of problems, such as many difficult mathematical ones. In this paper, we review some of the most important quantum algorithms for hard mathematical problems. When factoring large numbers, Shor's algorithm is orders of magnitude faster than any other known classical algorithm. The Grover's algorithm, which searches unsorted databases much more quickly than conventional algorithms, is then discussed.

International Journal on Recent and Innovation Trends in Computing and Communication•Nov 7, 2023•1 citation
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.
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.
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.
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.
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 power of quantum mechanics, that is too complex for conventional computers, can be solved by an innovative model of computing known as quantum computing. Quantum algorithms can provide exponential speedups for some types of problems, such as many difficult mathematical ones. In this paper, we review some of the most important quantum algorithms for hard mathematical problems. When factoring large numbers, Shor's algorithm is orders of magnitude faster than any other known classical algorithm. The Grover's algorithm, which searches unsorted databases much more quickly than conventional algorithms, is then discussed.