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

MATHEMATICAL ASPECTS OF SHOR'S ALGORITHM

Christophe Pittet

Published Nov 18, 2013• 1 citation
OpenAlex

Abstract

Abstract. Given a large n-bits integer N < 2n, Shor’s algorithm finds with positive probability a factor of N after O(n2 log n log log n) quantum steps. We describe some of the mathematical aspects of Shor’s algorithm. We mainly follow a description due to M. Batty, S.L. Braunstein, A. J. Duncan and S. Rees. 1.

Related papers

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

An Overview of Regev’s Quantum Factoring Algorithm and Its Recent Developments

Rick Lan Chen

Factoring large integers has long been a computationally difficult problem in classical computing, forming the foundation of widely used encryption methods like RSA. In 1994, Shor’s quantum algorithm introduced a revolutionary method for factoring integers exponentially faster than classical algorithms, laying the groundwork for quantum cryptography. Despite numerous attempts to enhance Shor’s algorithm over the last three decades, significant breakthroughs remained elusive until Regev’s discovery in 2023. Regev introduced a novel, multi-dimensional version of the quantum factoring algorithm, achieving a substantial improvement by reducing the required number of quantum gates to O(n^2 lo g⁡n )(n^(3/2) log⁡n ), compared to Shor’s originalO(n^2 lo g⁡n )original O(n^2 log⁡n ) gate complexity. Although Regev’s approach offers a significant speedup, it comes with increased qubit requirements and relies on an unproven number theory assumption. This paper presents an overview of Regev’s factoring algorithm, including a review of Shor’s work for context, followed by an examination of key recent developments and follow-up research. These include efforts to reduce the qubit count, improve error resilience, generalizegeneralise Regev’s algorithm to related problems, and validate the number theory assumption. This review serves as an accessible entry point for researchers interested in the rapidly evolving field of quantum computing and factoring algorithms.

Applied and Computational Engineering•Nov 28, 2024•2 citations

Distributed Shor's algorithm

Ligang Xiao, Daowen Qiu, Le Luo +1 more

Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm, the quantum part of which is to estimate $s/r$, where $r$ is the ``order" and $s$ is some natural number that less than $r$. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of $s/r$.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly $L/2$ qubits for factoring an $L$-bit integer and reduces the circuit depth of each computer.

arXiv:2207.05976•Quantum Information and Computation•Jan 1, 2023•39 citations

A simplification of the Shor quantum factorization algorithm employing a quantum Hadamard transform

Rupert C. D. Young, Philip M. Birch, Chris R. Chatwin

The Shor quantum factorization algorithm allows the factorization or large integers in logarithmic squared time whereas classical algorithms require an exponential time increase with the bit length of the number to be factored. The hardware implementation of the Shor algorithm would thus allow the factorization of the very large integers employed by commercial encryption methods. We propose some modifications of the algorithm by employing some simplification to the stage employing the quantum Fourier transform. The quantum Hadamard transform may be used to replace the quantum Fourier transform in certain cases. This would reduce the hardware complexity of implementation since phase rotation gates with only two states of 0 and π would be required.

Pattern Recognition and Tracking•Apr 27, 2018•5 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

Circuit for Shor's algorithm using 2n+3 qubits

Stéphane Beauregard

We try to minimize the number of qubits needed to factor an integer of n bits using Shor's algorithm on a quantum computer. We introduce a circuit which uses 2n+3 qubits and O(n^3 lg(n)) elementary quantum gates in a depth of O(n^3) to implement the factorization algorithm. The circuit is computable in polynomial time on a classical computer and is completely general as it does not rely on any property of the number to be factored.

arXiv:quant-ph/0205095•Quantum Information and Computation•Mar 1, 2003•299 citations
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.
Factoring large integers has long been a computationally difficult problem in classical computing, forming the foundation of widely used encryption methods like RSA. In 1994, Shor’s quantum algorithm introduced a revolutionary method for factoring integers exponentially faster than classical algorithms, laying the groundwork for quantum cryptography. Despite numerous attempts to enhance Shor’s algorithm over the last three decades, significant breakthroughs remained elusive until Regev’s discovery in 2023. Regev introduced a novel, multi-dimensional version of the quantum factoring algorithm, achieving a substantial improvement by reducing the required number of quantum gates to O(n^2 lo g⁡n )(n^(3/2) log⁡n ), compared to Shor’s originalO(n^2 lo g⁡n )original O(n^2 log⁡n ) gate complexity. Although Regev’s approach offers a significant speedup, it comes with increased qubit requirements and relies on an unproven number theory assumption. This paper presents an overview of Regev’s factoring algorithm, including a review of Shor’s work for context, followed by an examination of key recent developments and follow-up research. These include efforts to reduce the qubit count, improve error resilience, generalizegeneralise Regev’s algorithm to related problems, and validate the number theory assumption. This review serves as an accessible entry point for researchers interested in the rapidly evolving field of quantum computing and factoring algorithms.
Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm, the quantum part of which is to estimate s/rs/rs/r, where rrr is the ``order" and sss is some natural number that less than rrr. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of s/rs/rs/r.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly L/2L/2L/2 qubits for factoring an LLL-bit integer and reduces the circuit depth of each computer.
The Shor quantum factorization algorithm allows the factorization or large integers in logarithmic squared time whereas classical algorithms require an exponential time increase with the bit length of the number to be factored. The hardware implementation of the Shor algorithm would thus allow the factorization of the very large integers employed by commercial encryption methods. We propose some modifications of the algorithm by employing some simplification to the stage employing the quantum Fourier transform. The quantum Hadamard transform may be used to replace the quantum Fourier transform in certain cases. This would reduce the hardware complexity of implementation since phase rotation gates with only two states of 0 and π would be required.
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.