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:2309.10757

Integer Factorization by Quantum Measurements

Giuseppe Mussardo, Andrea Trombettoni

Published Sep 19, 2023• 3 citations
arXivHTMLPDF

Abstract

Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on ordinary classical computers. Their common feature is the use of genuine quantum properties such as entanglement and superposition of states. Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a polynomial-time quantum algorithm for integer factorization, with far reaching potential applications in several fields, such as cryptography. Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement. In this new scheme, the factorization of the integer $N$ is achieved in a number of steps equal to the number $k$ of its prime factors, -- e.g., if $N$ is the product of two primes, two quantum measurements are enough, regardless of the number of digits $n$ of the number $N$. Since $k$ is the lower bound to the number of operations one can do to factorize a general integer, one sees that a quantum mechanical setup can saturate such a bound.

DOI
10.48550/arxiv.2309.10757

Related papers

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

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

Proposing a Quantum simulator for integer factorization

José Luis Rosales, Vicente Martín Ayuso

Many cryptographic algorithms depend on computational complexity assumptions. Notorious cases are the RSA algorithm for public key criptography or the Diffie-Hellman key exchange protocol, to publicly agree on a common secret key. Both algorithms are known to be broken by quantum computing as well as those that can be reduced to a discrete logarithm problem. These are key algorithms in our digital society and are at the basis of everyday tasks, specially those that rely on digital signatures. The RSA algorithm, in particular, is probably the most used algorithm and is its assumed security the one that guards most of the e-commerce nowadays. In this case, it is the time complexity of finding the prime factors of a large number, that grows worse than polinomially with the size of the number, the main guardian of our cyberinfrastructure. The fact that a quantum computer can solve this problem in polynomial time using Shor's algorithm is seen as a potentially major disruption and has prompted security agencies to advice the progressive deprecation of these algorithms.

•Jan 1, 2016•0 citations

Analysis of Quantum Algorithm to Find the Solution of Integer factoriza-tion Problem

Anil Kumar Malviya, Lokendra Singh Umrao Vibhooti Singh

Quantum computing has emerged as an important interdisciplinary field, merging theories in mathematics, physics and computer science. So far, a significant portion of research in quantum computing has focused on the design of quantum algorithms. Quantum Com-puters requires very different algorithms for factorization, which plays an important role in the field of quantum computing and shor’s algo-rithm is used to address integer factorization problem. Shor's algorithm is important because it breaks a widely used public-key cryptography scheme known as RSA. This paper discusses the refinement of quantum factorization algorithm. Keywords: - quantum algorithm, factorization, gcd, prime decomposition, shor’s algorithm.

International Journal of Advanced Research in Computer Science•Jan 1, 2011•0 citations

Quantum Integer Factorization by 3 Different Methods, Their Implementations and Results

Jiří Tomčala

The content of this poster is a description of the implementation of two well-known quantum integer factorization methods and, in addition, a proposal of a new, third way along with some examples of its use. For all three methods, the measured results of their circuits will be shown.The first method is Shor's algorithm, where a quantum circuit is used only to find the period of a specially assembled modular exponentiating function. The rest of the algorithm is preprocessing and postprocessing that can be done on a classical computer, so one could say that this is a hybrid algorithm. New results of the successful factorization of the number 119, performed by this algorithm on a real 7-qubit quantum computer, will be presented. It is worth mentioning here that the highest number successfully factorized by this algorithm on a real quantum computer so far was 35.The second method is variational quantum factorization (VQF). In this method, preprocessing builds a system of equations based on the classical binary multiplication procedure of two numbers, resulting in a factorized number. This system of equations is then used to form a Hamiltonian in such a way that its ground state corresponds to the solution of this equation system. Only now the hybrid quantum optimization comes into play to iteratively find this ground state. The advantage over Shor's algorithm is that this method does not require a fault-tolerant quantum computer, but on the other hand it approaches the solution iteratively using a classical computer, which reduces the potential quantum advantage.The new, third method employs Grover's search algorithm in an unusual way to create a quantum factorization circuit. A key part of this approach is the quantum implementation of a multiplying oracle. The main advantage of this method over the previous ones is that it can be used to assemble a relatively simple universal factorization circuit. Moreover, there is almost no preprocessing and postprocessing required. This method is still under development, but this poster will present the first results.

•Dec 18, 2025•0 citations

Shor's factorization algorithm

E. Desurvire

This chapter describes what is generally considered to be one of the most important and historical contributions to the field of quantum computing, namely Shor's factorization algorithm . As its name indicates, this algorithm makes it possible to factorize numbers, which consists in their decomposition into a unique product of prime numbers. Other classical factorization algorithms previously developed have a complexity or computing time that increases exponentially with the number size, making the task intractable if not hopeless for large numbers. In contrast, Shor's algorithm is able to factor a number of any size in polynomial time , making the factorization problem tractable should a quantum computer ever be realized in the future. Since Shor's algorithm is based on several nonintuitive properties and other mathematical subtleties, this chapter presents a certain level of difficulty. With the previous chapters and tools readily assimilated, and some patience in going through the different preliminary steps required, such a difficulty is, however, quite surmountable. I have sought to make this description of Shor's algorithm as mathematically complete as possible and crack-free, while avoiding some academic considerations that may not be deemed necessary from any engineering perspective. Eventually, Shor's algorithm is described in only a few basic instructions. What is conceptually challenging is to grasp why it works so well, and also to feel comfortable with the fact that its implementation actually takes a fair amount of trial and error. The two preliminaries of Shor's algorithm are the phase estimation and the related order-finding algorithms.

Cambridge University Press eBooks•Feb 19, 2009•0 citations
Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on ordinary classical computers. Their common feature is the use of genuine quantum properties such as entanglement and superposition of states. Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a polynomial-time quantum algorithm for integer factorization, with far reaching potential applications in several fields, such as cryptography. Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement. In this new scheme, the factorization of the integer NNN is achieved in a number of steps equal to the number kkk of its prime factors, -- e.g., if NNN is the product of two primes, two quantum measurements are enough, regardless of the number of digits nnn of the number NNN. Since kkk is the lower bound to the number of operations one can do to factorize a general integer, one sees that a quantum mechanical setup can saturate such a bound.
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 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.
Many cryptographic algorithms depend on computational complexity assumptions. Notorious cases are the RSA algorithm for public key criptography or the Diffie-Hellman key exchange protocol, to publicly agree on a common secret key. Both algorithms are known to be broken by quantum computing as well as those that can be reduced to a discrete logarithm problem. These are key algorithms in our digital society and are at the basis of everyday tasks, specially those that rely on digital signatures. The RSA algorithm, in particular, is probably the most used algorithm and is its assumed security the one that guards most of the e-commerce nowadays. In this case, it is the time complexity of finding the prime factors of a large number, that grows worse than polinomially with the size of the number, the main guardian of our cyberinfrastructure. The fact that a quantum computer can solve this problem in polynomial time using Shor's algorithm is seen as a potentially major disruption and has prompted security agencies to advice the progressive deprecation of these algorithms.
Quantum computing has emerged as an important interdisciplinary field, merging theories in mathematics, physics and computer science. So far, a significant portion of research in quantum computing has focused on the design of quantum algorithms. Quantum Com-puters requires very different algorithms for factorization, which plays an important role in the field of quantum computing and shor’s algo-rithm is used to address integer factorization problem. Shor's algorithm is important because it breaks a widely used public-key cryptography scheme known as RSA. This paper discusses the refinement of quantum factorization algorithm. Keywords: - quantum algorithm, factorization, gcd, prime decomposition, shor’s algorithm.
The content of this poster is a description of the implementation of two well-known quantum integer factorization methods and, in addition, a proposal of a new, third way along with some examples of its use. For all three methods, the measured results of their circuits will be shown.The first method is Shor's algorithm, where a quantum circuit is used only to find the period of a specially assembled modular exponentiating function. The rest of the algorithm is preprocessing and postprocessing that can be done on a classical computer, so one could say that this is a hybrid algorithm. New results of the successful factorization of the number 119, performed by this algorithm on a real 7-qubit quantum computer, will be presented. It is worth mentioning here that the highest number successfully factorized by this algorithm on a real quantum computer so far was 35.The second method is variational quantum factorization (VQF). In this method, preprocessing builds a system of equations based on the classical binary multiplication procedure of two numbers, resulting in a factorized number. This system of equations is then used to form a Hamiltonian in such a way that its ground state corresponds to the solution of this equation system. Only now the hybrid quantum optimization comes into play to iteratively find this ground state. The advantage over Shor's algorithm is that this method does not require a fault-tolerant quantum computer, but on the other hand it approaches the solution iteratively using a classical computer, which reduces the potential quantum advantage.The new, third method employs Grover's search algorithm in an unusual way to create a quantum factorization circuit. A key part of this approach is the quantum implementation of a multiplying oracle. The main advantage of this method over the previous ones is that it can be used to assemble a relatively simple universal factorization circuit. Moreover, there is almost no preprocessing and postprocessing required. This method is still under development, but this poster will present the first results.
This chapter describes what is generally considered to be one of the most important and historical contributions to the field of quantum computing, namely Shor's factorization algorithm . As its name indicates, this algorithm makes it possible to factorize numbers, which consists in their decomposition into a unique product of prime numbers. Other classical factorization algorithms previously developed have a complexity or computing time that increases exponentially with the number size, making the task intractable if not hopeless for large numbers. In contrast, Shor's algorithm is able to factor a number of any size in polynomial time , making the factorization problem tractable should a quantum computer ever be realized in the future. Since Shor's algorithm is based on several nonintuitive properties and other mathematical subtleties, this chapter presents a certain level of difficulty. With the previous chapters and tools readily assimilated, and some patience in going through the different preliminary steps required, such a difficulty is, however, quite surmountable. I have sought to make this description of Shor's algorithm as mathematically complete as possible and crack-free, while avoiding some academic considerations that may not be deemed necessary from any engineering perspective. Eventually, Shor's algorithm is described in only a few basic instructions. What is conceptually challenging is to grasp why it works so well, and also to feel comfortable with the fact that its implementation actually takes a fair amount of trial and error. The two preliminaries of Shor's algorithm are the phase estimation and the related order-finding algorithms.