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:1304.0128 · Scientific Reports

Factoring 51 and 85 with 8 qubits

Michael R. Geller, Zhongyuan Zhou

Published Oct 28, 2013• 27 citations
arXivHTMLPDF

Abstract

We construct simplified quantum circuits for Shor's order-finding algorithm for composites N given by products of the Fermat primes 3, 5, 17, 257, and 65537. Such composites, including the previously studied case of 15, as well as 51, 85, 771, 1285, 4369, … have the simplifying property that the order of a modulo N for every base a coprime to N is a power of 2, significantly reducing the usual phase estimation precision requirement. Prime factorization of 51 and 85 can be demonstrated with only 8 qubits and a modular exponentiation circuit consisting of no more than four CNOT gates.

DOI
10.1038/srep03023

Related papers

Shor's Factoring Algorithm and Modular Exponentiation Operators

Robert Singleton

We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.

arXiv:2306.09122•Quanta•Sep 15, 2023•15 citations

Quantum Factoring Algorithm: Resource Estimation and Survey of Experiments

Noboru Kunihiro

Abstract It is known that Shor’s algorithm can break many cryptosystems such as RSA encryption, provided that large-scale quantum computers are realized. Thus far, several experiments for the factorization of the small composites such as 15 and 21 have been conducted using small-scale quantum computers. In this study, we investigate the details of quantum circuits used in several factoring experiments. We then indicate that some of the circuits have been constructed under the condition that the order of an element modulo a target composite is known in advance. Because the order must be unknown in the experiments, they are inappropriate for designing the quantum circuit of Shor’s factoring algorithm. We also indicate that the circuits used in the other experiments are constructed by relying considerably on the target composite number to be factorized.

Mathematics for industry•Oct 22, 2020•2 citations

Faster quantum number factoring via circuit synthesis

Igor L. Markov, Mehdi Saeedi

A major obstacle to implementing Shor's quantum number-factoring algorithm is the large size of modular-exponentiation circuits. We reduce this bottleneck by customizing reversible circuits for modular multiplication to individual runs of Shor's algorithm. Our circuit-synthesis procedure exploits spectral properties of multiplication operators and constructs optimized circuits from the traces of the execution of an appropriate greatest-common-divisor algorithm. Empirically, gate counts are reduced by four to five times, and circuit latency is reduced by larger factors.

arXiv:1301.3210•Physical Review A•Jan 14, 2013•32 citations

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•18 citations

Constant-optimized quantum circuits for modular multiplication and exponentiation

Igor L. Markov, Mehdi Saeedi

Reversible circuits for modular multiplication $Cx\%M$ with $x<M$ arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific $C$ and $M$ values. In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient $C$ values. When zero-initialized ancilla registers are available, we reduce the search for compact circuits to a shortest-path problem. Some of our modular-multiplication circuits are asymptotically smaller than previous constructions, but worst-case bounds and average sizes remain $\Theta(n^2)$. In the context of modular exponentiation, we offer several constant-factor improvements, as well as an improvement by a constant additive term that is significant for few-qubit circuits arising in ongoing laboratory experiments with Shor's algorithm.

arXiv:1202.6614•Quantum Information and Computation•May 1, 2012•125 citations

Implementing Shor’s algorithm on Josephson charge qubits

Juha J. Vartiainen, A. O. Niskanen, Mikio Nakahara +1 more

We investigate the physical implementation of Shor's factorization algorithm on a Josephson charge qubit register. While we pursue a universal method to factor a composite integer of any size, the scheme is demonstrated for the number 21. We consider both the physical and algorithmic requirements for an optimal implementation when only a small number of qubits are available. These aspects of quantum computation are usually the topics of separate research communities; we present a unifying discussion of both of these fundamental features bridging Shor's algorithm to its physical realization using Josephson junction qubits. In order to meet the stringent requirements set by a short decoherence time, we accelerate the algorithm by decomposing the quantum circuit into tailored two- and three-qubit gates and we find their physical realizations through numerical optimization.

arXiv:quant-ph/0308171•Physical Review A•Jul 30, 2004•23 citations
We construct simplified quantum circuits for Shor's order-finding algorithm for composites N given by products of the Fermat primes 3, 5, 17, 257, and 65537. Such composites, including the previously studied case of 15, as well as 51, 85, 771, 1285, 4369, … have the simplifying property that the order of a modulo N for every base a coprime to N is a power of 2, significantly reducing the usual phase estimation precision requirement. Prime factorization of 51 and 85 can be demonstrated with only 8 qubits and a modular exponentiation circuit consisting of no more than four CNOT gates.
We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.
Abstract It is known that Shor’s algorithm can break many cryptosystems such as RSA encryption, provided that large-scale quantum computers are realized. Thus far, several experiments for the factorization of the small composites such as 15 and 21 have been conducted using small-scale quantum computers. In this study, we investigate the details of quantum circuits used in several factoring experiments. We then indicate that some of the circuits have been constructed under the condition that the order of an element modulo a target composite is known in advance. Because the order must be unknown in the experiments, they are inappropriate for designing the quantum circuit of Shor’s factoring algorithm. We also indicate that the circuits used in the other experiments are constructed by relying considerably on the target composite number to be factorized.
A major obstacle to implementing Shor's quantum number-factoring algorithm is the large size of modular-exponentiation circuits. We reduce this bottleneck by customizing reversible circuits for modular multiplication to individual runs of Shor's algorithm. Our circuit-synthesis procedure exploits spectral properties of multiplication operators and constructs optimized circuits from the traces of the execution of an appropriate greatest-common-divisor algorithm. Empirically, gate counts are reduced by four to five times, and circuit latency is reduced by larger factors.
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.
Reversible circuits for modular multiplication Cx%MCx\%MCx%M with x<Mx<Mx<M arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific CCC and MMM values. In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient CCC values. When zero-initialized ancilla registers are available, we reduce the search for compact circuits to a shortest-path problem. Some of our modular-multiplication circuits are asymptotically smaller than previous constructions, but worst-case bounds and average sizes remain Θ(n2)\Theta(n^2)Θ(n2). In the context of modular exponentiation, we offer several constant-factor improvements, as well as an improvement by a constant additive term that is significant for few-qubit circuits arising in ongoing laboratory experiments with Shor's algorithm.
We investigate the physical implementation of Shor's factorization algorithm on a Josephson charge qubit register. While we pursue a universal method to factor a composite integer of any size, the scheme is demonstrated for the number 21. We consider both the physical and algorithmic requirements for an optimal implementation when only a small number of qubits are available. These aspects of quantum computation are usually the topics of separate research communities; we present a unifying discussion of both of these fundamental features bridging Shor's algorithm to its physical realization using Josephson junction qubits. In order to meet the stringent requirements set by a short decoherence time, we accelerate the algorithm by decomposing the quantum circuit into tailored two- and three-qubit gates and we find their physical realizations through numerical optimization.