Shor's algorithm

Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor.^[1]

On a quantum computer, to factor an integer $N$ , Shor's algorithm runs in polylogarithmic time, meaning the time taken is polynomial in $\log N$ , the size of the integer given as input.^[2] Specifically, it takes quantum gates of order $O\!\left((\log N)^{2}(\log \log N)(\log \log \log N)\right)$ using fast multiplication,^[3] or even $O\!\left((\log N)^{2}(\log \log N)\right)$ utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey and Van Der Hoven,^[4] thus demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is consequently in the complexity class BQP. This is significantly faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time: $O\!\left(e^{1.9(\log N)^{1/3}(\log \log N)^{2/3}}\right)$ .^[5]

If a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor's algorithm could be used to break public-key cryptography schemes, such as

The RSA scheme
The Finite Field Diffie-Hellman key exchange
The Elliptic Curve Diffie-Hellman key exchange^[6]

RSA is based on the assumption that factoring large integers is computationally intractable. As far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor integers in polynomial time. However, Shor's algorithm shows that factoring integers is efficient on an ideal quantum computer, so it may be feasible to defeat RSA by constructing a large quantum computer. It was also a powerful motivator for the design and construction of quantum computers, and for the study of new quantum-computer algorithms. It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called post-quantum cryptography.

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored $15$ into $3\times 5$ , using an NMR implementation of a quantum computer with $7$ qubits.^[7] After IBM's implementation, two independent groups implemented Shor's algorithm using photonic qubits, emphasizing that multi-qubit entanglement was observed when running the Shor's algorithm circuits.^[8]^[9] In 2012, the factorization of $15$ was performed with solid-state qubits.^[10] Later, in 2012, the factorization of $21$ was achieved.^[11] In 2019, an attempt was made to factor the number $35$ using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors.^[12] Though larger numbers have been factored by quantum computers using other algorithms,^[13] these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms.^[14]

Procedure

The problem that we are trying to solve is, given an odd composite number $N$ , to factor $N$ .

Shor's algorithm consists of two parts:

A classical reduction of the factoring problem to the problem of order-finding.
A quantum algorithm to solve the order-finding problem.

The reduction in Shor's factoring algorithm is similar to other factoring algorithms, such as the quadratic sieve.

Classical part

A complete factoring algorithm is possible using extra classical methods if we're able to factor $N$ into just two integers $p$ and $q$ ^{[citation needed]}; therefore the algorithm only needs to achieve that.

First, we can check whether $N$ is even. The rest of the algorithm requires that $N$ is odd, and if it's even, we have found a nontrivial factor of $N$ . Afterwards, we can use efficient classical algorithms to check if $N$ is a prime power^{[citation needed]}; again, the rest of the algorithm requires that $N$ is not a prime power^{[citation needed]}, and if it is, $N$ has been completely factored.

If those easy cases do not produce a nontrivial factor of $N$ , the algorithm proceeds to handle the remaining case. We pick a random integer $2\leq a<N$ . A possible nontrivial divisor of $N$ can be found by computing $\gcd(a,N)$ , which can be done classically and efficiently using the Euclidean algorithm. If this produces a nontrivial factor (meaning $\gcd(a,N)\neq 1$ ), the algorithm is finished, and the other nontrivial factor is ${\textstyle {\frac {N}{\gcd(a,N)}}}$ . If a nontrivial factor was not identified, then that means that $N$ and the choice of $a$ are coprime. Here, the algorithm runs the quantum subroutine, which will return the order $r$ of $a$ , meaning

a^{r}\equiv 1{\bmod {N}}.

The quantum subroutine requires that $a$ and $N$ are coprime^{[citation needed]}, which is true since at this point in the algorithm, $\gcd(a,N)$ did not produce a nontrivial factor of $N$ . It can be seen from the equivalence that $N$ divides $a^{r}-1$ , written $N\mid a^{r}-1$ . This can be factored using difference of squares:

N\mid (a^{r/2}-1)(a^{r/2}+1)

Since we have factored the expression in this way, the algorithm doesn't work for odd

r

(because

a^{r/2}

must be an integer), meaning the algorithm would have to restart with a new

a

. Hereafter we can therefore assume

r

is even. It cannot be the case that

N\mid a^{r/2}-1

, since this would imply

a^{r/2}\equiv 1{\bmod {N}}

, which would contradictorily imply that

{\textstyle {\frac {r}{2}}}

would be the order of

a

, which was already

r

. At this point, it may or may not be the case that

N\mid a^{r/2}+1

. If it is not true that

N\mid a^{r/2}+1

, then that means we are able to find a nontrivial factor of

N

. We compute

d=\gcd(N,a^{r/2}-1)

If

d=1

, then that means

N\mid a^{r/2}+1

was true, and a nontrivial factor of

N

cannot be achieved from

a

, and the algorithm must restart with a new

a

. Otherwise, we have found a nontrivial factor of

N

, with the other being

{\textstyle {\frac {N}{d}}}

, and the algorithm is finished. For this step, it is also equivalent to compute

\gcd(N,a^{r/2}+1)

; it will produce a nontrivial factor if

\gcd(N,a^{r/2}-1)

is nontrivial, and will not if it's trivial (where

N\mid a^{r/2}+1

).

The algorithm restated shortly follows: let $N$ be odd, and not a prime power. We want to output two nontrivial factors of $N$ .

Pick a random number $1<a<N$ .
Compute $K=\gcd(a,N)$ , the greatest common divisor of $a$ and $N$ .
If $K\neq 1$ , then $K$ is a nontrivial factor of $N$ , with the other factor being ${\textstyle {\frac {N}{K}}}$ and we are done.
Otherwise, use the quantum subroutine to find the order $r$ of $a$ .
If $r$ is odd, then go back to step 1.
Compute $g=\gcd(N,a^{r/2}+1)$ . If $g$ is nontrivial, the other factor is ${\textstyle {\frac {N}{g}}}$ , and we're done. Otherwise, go back to step 1.

It has been shown that this will be likely to succeed after a few runs^{[citation needed]}.

Quantum order-finding subroutine

Quantum subroutine in Shor's algorithm

The quantum subroutine of Shor's algorithm can be expressed as an application of quantum phase estimation. This connection with quantum phase estimation was not discussed in the original formulation of Shor's algorithm,^[15] but was later proposed by Kitaev.^[16] The goal of the quantum subroutine is to solve the following problem: given coprime integers $N$ and $1<a<N$ , find the smallest positive integer $r$ such that $a^{r}\equiv 1{\pmod {N}}$ . The quantum circuit is then built based on each choice of such $a,N$ , and uses two registers. The second register uses $n$ qubits where $n$ is the smallest integer such that $N\leq 2^{n}$ . The size of the first register determines how accurate of an approximation the circuit produces. It can be shown that using $2n$ qubits gives sufficient accuracy to find $r$ .

In general, the quantum phase estimation algorithm can be summarized as follows: given a unitary $U$ , one can efficiently construct a quantum circuit which sends inputs states $|0\rangle |\psi \rangle$ into output states close to $|\phi \rangle |\psi \rangle$ for each $j$ , where $|\phi\rangle$ is an approximation to $2^{n}\theta$ , where $\theta$ is the corresponding eigenvalue of $|\psi \rangle$ in $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle$ . In other words, it sends each eigenstate $|\psi _{j}\rangle$ of $U$ into a state close to the associated eigenvalue. For the purposes of quantum order-finding, we employ this strategy using the unitary defined by the action:

U|k\rangle ={\begin{cases}|ak{\pmod {N}}\rangle &0\leq k<N,\\|k\rangle &N\leq k<2^{n}.\end{cases}}

The states $N\leq k<2^{n}$ are not important; their rule is given just to have the transformation be well defined. The operation is reversible, and therefore implementable on a quantum computer. The transformation $U^{2^{j}}$ must be efficiently implementable to perform the algorithm. This is accomplished by modular exponentiation, which is the slowest part of the algorithm. Now we must choose ${\textstyle |\psi \rangle }$ . We define the following eigenvector of ${\textstyle U}$ :

|\psi _{j}\rangle ={\frac {1}{\sqrt {r}}}{\bigl (}|1\rangle +\omega _{r}^{-j}|a\rangle +\omega _{r}^{-2j}|a^{2}\rangle +\ldots +\omega _{r}^{-j(r-1)}|a^{r-1}\rangle {\bigr )}

where

{\textstyle 0\leq j<r}

, and

{\textstyle \omega _{r}^{k}=e^{2\pi i{\frac {k}{r}}}}

, which is one of the

r

-th roots of unity.

{\textstyle |\psi _{j}\rangle }

has an eigenvalue of

{\textstyle \omega _{r}^{j}}

. We are unable to construct each individual

{\textstyle |\psi _{j}\rangle ,}

but it turns out the superposition of all

r

eigenvectors is just the

{\textstyle |1\rangle }

state. This can be seen from the following:

{\begin{aligned}{\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\psi _{j}\rangle &={\frac {1}{r}}\sum _{j=0}^{r-1}\sum _{k=0}^{r-1}\omega _{r}^{jk}|a^{k}\rangle \\&={\frac {1}{r}}\sum _{k=0}^{r-1}\left(\sum _{j=0}^{r-1}\omega _{r}^{jk}\right)|a^{k}\rangle \\&=|1\rangle +{\frac {1}{r}}\sum _{k=1}^{r-1}\left(\sum _{j=0}^{r-1}\omega _{r}^{jk}\right)|a^{k}\rangle \\\end{aligned}}

The right term simplifies to

0

, since the roots of unity sum to zero:

\sum _{j=0}^{r-1}\omega _{r}^{jk}=0

which can be verified using the geometric series formula. Therefore the superposition of all

{\textstyle |\psi _{j}\rangle }

states is just

{\textstyle |1\rangle }

(this is the

{\textstyle |1\rangle }

state with

{\textstyle n}

qubits, since

U

is defined on a register of size

2^{n}

). Essentially, we are running phase estimation on a superposition of eigenvectors. This does have effects on measurement, but they are avoidable. Now all the parameters of the phase estimation circuit have been specified, and the algorithm can be run.

Let ${\textstyle {\mathcal {A}}}$ represent the overall transformation that quantum phase estimation applies, right before measurement of the first register. For a singular $|\psi _{j}\rangle$ , ${\textstyle {\mathcal {A}}}$ would apply the transformation

|0\rangle ^{\otimes n}|\psi _{j}\rangle \mapsto |\phi _{j}\rangle |\psi _{j}\rangle

where

{\textstyle |\phi _{j}\rangle }

is a superposition that will be measured to derive an approximation of the phase

{\textstyle {\frac {j}{r}}}

. When we use

{\textstyle |1\rangle }

for our eigenvector, the same thing occurs, but on a superposition of each

{\textstyle |\psi _{j}\rangle }

. The initial state of the algorithm is

|0\rangle ^{\otimes n}|1\rangle ={\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|0\rangle ^{\otimes n}|\psi _{j}\rangle

The circuit will apply

{\textstyle {\mathcal {A}}}

to this state:

{\begin{aligned}{\mathcal {A}}\left({\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|0\rangle ^{\otimes n}|\psi _{j}\rangle \right)&={\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}{\mathcal {A}}|0\rangle ^{\otimes n}|\psi _{j}\rangle \\&={\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\phi _{j}\rangle |\psi _{j}\rangle \end{aligned}}

Then the first register will be measured, with each

{\textstyle |\phi _{j}\rangle }

having an equal probability

{\textstyle {\frac {1}{r}}}

of being measured. Each

{\textstyle |\phi _{j}\rangle }

will produce an integer approximation to

{\textstyle {\frac {j}{r}}2^{n}}

, which can be divided by

{\textstyle 2^{n}}

to get a decimal approximation for

{\textstyle {\frac {j}{r}}}

. Then, we apply the continued fractions algorithm to find integers

{\textstyle b}

and

{\textstyle c}

, where

{\textstyle {\frac {b}{c}}}

gives the best fraction approximation for the approximation measured from the circuit, for

{\textstyle b,c<N}

and coprime

{\textstyle b}

and

{\textstyle c}

. The number of qubits in the first register,

2n

, which determines the accuracy of the approximation, guarantees that

{\frac {b}{c}}={\frac {j}{r}}

given the best approximation from the superposition of

{\textstyle |\phi _{j}\rangle }

was measured^{[citation needed]} (which can be made arbitrarily likely by using extra bits and truncating the output). However, while

{\textstyle b}

and

{\textstyle c}

are coprime, it may be the case that

{\textstyle j}

and

{\textstyle r}

are not coprime. Because of that,

{\textstyle b}

and

{\textstyle c}

may have lost some factors that were in

{\textstyle j}

and

{\textstyle r}

. This can be remedied by rerunning the quantum subroutine an arbitrary number of times, to produce a list of fraction approximations

{\frac {b_{1}}{c_{1}}}_{\textstyle ,}\;{\frac {b_{2}}{c_{2}}}_{\textstyle ,}\ldots {\vphantom {\frac {b_{1}}{c_{1}}}}_{\textstyle ,}\;{\frac {b_{s}}{c_{s}}}

where

{\textstyle s}

is the number of times the algorithm was run. Each

{\textstyle c_{k}}

will have different factors taken out of it because the circuit will (likely) have measured multiple different possible values of

{\textstyle j}

. To recover the actual

{\textstyle r}

value, we can take the least common multiple of each

{\textstyle c_{k}}

:

\mathrm {lcm} (c_{1},c_{2},\ldots ,c_{s})

The least common multiple will be the order

{\textstyle r}

of the original integer

{\textstyle a}

with high probability.

The bottleneck

The runtime bottleneck of Shor's algorithm is quantum modular exponentiation, which is by far slower than the quantum Fourier transform and classical pre-/post-processing. There are several approaches to constructing and optimizing circuits for modular exponentiation. The simplest and (currently) most practical approach is to mimic conventional arithmetic circuits with reversible gates, starting with ripple-carry adders. Knowing the base and the modulus of exponentiation facilitates further optimizations.^[17]^[18] Reversible circuits typically use on the order of $n^{3}$ gates for $n$ qubits. Alternative techniques asymptotically improve gate counts by using quantum Fourier transforms, but are not competitive with fewer than 600 qubits owing to high constants.

Discrete logarithms

Given a group $G$ with order $p$ and generator $g \in G$ , suppose we know that $x=g^{r}\in G$ , for some $r\in \mathbb {Z} _{p}$ , and we wish to compute $r$ , which is the discrete logarithm: $r={\log _{g}}(x)$ . Consider the abelian group $\mathbb {Z} _{p}\times \mathbb {Z} _{p}$ , where each factor corresponds to modular addition of values. Now, consider the function

f\colon \mathbb {Z} _{p}\times \mathbb {Z} _{p}\to G\;;\;f(a,b)=g^{a}x^{-b}.

This gives us an abelian hidden subgroup problem, as $f$ corresponds to a group homomorphism. The kernel corresponds to the multiples of $(r,1)$ . So, if we can find the kernel, we can find $r$ . A quantum algorithm for solving this problem exists. This algorithm is, like the factor-finding algorithm, due to Peter Shor and both are implemented by creating a superposition through using Hadamard gates, followed by implementing $f$ as a quantum transform, followed finally by a quantum Fourier transform.^[19] Due to this, the quantum algorithm for computing the discrete logarithm is also occasionally referred to as "Shor's Algorithm."

The order-finding problem can also be viewed as a hidden subgroup problem.^[19] To see this, consider the group of integers under addition, and for a given $a\in \mathbb {Z}$ such that: $a^{r}=1$ , the function

f\colon \mathbb {Z} \to \mathbb {Z} \;;\;f(x)=a^{x},\;f(x+r)=f(x).

For any finite abelian group G, a quantum algorithm exists for solving the hidden subgroup for G in polynomial time.^[19]

References

^ Shor, P.W. (1994). "Algorithms for quantum computation: discrete logarithms and factoring". Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press: 124–134. doi:10.1109/sfcs.1994.365700. ISBN 0818665807. S2CID 15291489.
^ See also pseudo-polynomial time.
^ Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1996). "Efficient Networks for Quantum Factoring" (PDF). Physical Review A. 54 (2): 1034–1063. arXiv:quant-ph/9602016. Bibcode:1996PhRvA..54.1034B. doi:10.1103/PhysRevA.54.1034. PMID 9913575. S2CID 2231795.
^ Harvey, David; van Der Hoeven, Joris (2020). "Integer multiplication in time O(n log n)". Annals of Mathematics. doi:10.4007/annals.2021.193.2.4. S2CID 109934776.
^ "Number Field Sieve". wolfram.com. Retrieved 23 October 2015.
^ Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin E. (2017). "Quantum resource estimates for computing elliptic curve discrete logarithms". In Takagi, Tsuyoshi; Peyrin, Thomas (eds.). Advances in Cryptology – ASIACRYPT 2017 – 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3–7, 2017, Proceedings, Part II. Lecture Notes in Computer Science. Vol. 10625. Springer. pp. 241–270. arXiv:1706.06752. doi:10.1007/978-3-319-70697-9_9.
^ Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H. & Chuang, Isaac L. (2001), "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance" (PDF), Nature, 414 (6866): 883–887, arXiv:quant-ph/0112176, Bibcode:2001Natur.414..883V, CiteSeerX 10.1.1.251.8799, doi:10.1038/414883a, PMID 11780055, S2CID 4400832
^ Lu, Chao-Yang; Browne, Daniel E.; Yang, Tao & Pan, Jian-Wei (2007), "Demonstration of a Compiled Version of Shor's Quantum Factoring Algorithm Using Photonic Qubits" (PDF), Physical Review Letters, 99 (25): 250504, arXiv:0705.1684, Bibcode:2007PhRvL..99y0504L, doi:10.1103/PhysRevLett.99.250504, PMID 18233508, S2CID 5158195
^ Lanyon, B. P.; Weinhold, T. J.; Langford, N. K.; Barbieri, M.; James, D. F. V.; Gilchrist, A. & White, A. G. (2007), "Experimental Demonstration of a Compiled Version of Shor's Algorithm with Quantum Entanglement" (PDF), Physical Review Letters, 99 (25): 250505, arXiv:0705.1398, Bibcode:2007PhRvL..99y0505L, doi:10.1103/PhysRevLett.99.250505, hdl:10072/21608, PMID 18233509, S2CID 10010619
^ Lucero, Erik; Barends, Rami; Chen, Yu; Kelly, Julian; Mariantoni, Matteo; Megrant, Anthony; O'Malley, Peter; Sank, Daniel; Vainsencher, Amit; Wenner, James; White, Ted; Yin, Yi; Cleland, Andrew N.; Martinis, John M. (2012). "Computing prime factors with a Josephson phase qubit quantum processor". Nature Physics. 8 (10): 719. arXiv:1202.5707. Bibcode:2012NatPh...8..719L. doi:10.1038/nphys2385. S2CID 44055700.
^ Martín-López, Enrique; Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (12 October 2012). "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. 6 (11): 773–776. arXiv:1111.4147. Bibcode:2012NaPho...6..773M. doi:10.1038/nphoton.2012.259. S2CID 46546101.
^ Amico, Mirko; Saleem, Zain H.; Kumph, Muir (2019-07-08). "An Experimental Study of Shor's Factoring Algorithm on IBM Q". Physical Review A. 100 (1): 012305. arXiv:1903.00768. doi:10.1103/PhysRevA.100.012305. ISSN 2469-9926. S2CID 92987546.
^ Karamlou, Amir H.; Simon, William A.; Katabarwa, Amara; Scholten, Travis L.; Peropadre, Borja; Cao, Yudong (2021-10-28). "Analyzing the performance of variational quantum factoring on a superconducting quantum processor". npj Quantum Information. 7 (1): 156. arXiv:2012.07825. Bibcode:2021npjQI...7..156K. doi:10.1038/s41534-021-00478-z. ISSN 2056-6387. S2CID 229156747.
^ "Quantum computing motte-and-baileys". Shtetl-Optimized. 2019-12-28. Retrieved 2021-11-15.
^ Shor, Peter W. (October 1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/S0097539795293172. ISSN 0097-5397. S2CID 2337707.
^ Kitaev, A. Yu (1995-11-20). "Quantum measurements and the Abelian Stabilizer Problem". arXiv:quant-ph/9511026.
^ Markov, Igor L.; Saeedi, Mehdi (2012). "Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation". Quantum Information and Computation. 12 (5–6): 361–394. arXiv:1202.6614. Bibcode:2012arXiv1202.6614M. doi:10.26421/QIC12.5-6-1. S2CID 16595181.
^ Markov, Igor L.; Saeedi, Mehdi (2013). "Faster Quantum Number Factoring via Circuit Synthesis". Phys. Rev. A. 87 (1): 012310. arXiv:1301.3210. Bibcode:2013PhRvA..87a2310M. doi:10.1103/PhysRevA.87.012310. S2CID 2246117.
^ ^a ^b ^c Nielsen, Michael A.; Chuang, Isaac L. (9 December 2010). Quantum Computation and Quantum Information (PDF) (7th ed.). Cambridge University Press. ISBN 978-1-107-00217-3. Archived (PDF) from the original on 2019-07-11. Retrieved 24 April 2022.
^ Bernstein, Daniel J.; Heninger, Nadia; Lou, Paul; Valenta, Luke (2017). "Post-quantum RSA" (PDF). International Workshop on Post-Quantum Cryptography. Lecture Notes in Computer Science. 10346: 311–329. doi:10.1007/978-3-319-59879-6_18. ISBN 978-3-319-59878-9. Archived (PDF) from the original on 2017-04-20.

External links

Version 1.0.0 of libquantum: contains a C language implementation of Shor's algorithm with their simulated quantum computer library, but the width variable in shor.c should be set to 1 to improve the runtime complexity.
PBS Infinite Series created two videos explaining the math behind Shor's algorithm, "How to Break Cryptography" and "Hacking at Quantum Speed with Shor's Algorithm".

[1] Shor, P.W. (1994). "Algorithms for quantum computation: discrete logarithms and factoring". Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press: 124–134. doi:10.1109/sfcs.1994.365700. ISBN 0818665807. S2CID 15291489.

[2] See also pseudo-polynomial time.

[Beckman-3] Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1996). "Efficient Networks for Quantum Factoring" (PDF). Physical Review A. 54 (2): 1034–1063. arXiv:quant-ph/9602016. Bibcode:1996PhRvA..54.1034B. doi:10.1103/PhysRevA.54.1034. PMID 9913575. S2CID 2231795.

[Integer_multiplication_in_time_<math-4] Harvey, David; van Der Hoeven, Joris (2020). "Integer multiplication in time O(n log n)". Annals of Mathematics. doi:10.4007/annals.2021.193.2.4. S2CID 109934776.

[5] "Number Field Sieve". wolfram.com. Retrieved 23 October 2015.

[6] Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin E. (2017). "Quantum resource estimates for computing elliptic curve discrete logarithms". In Takagi, Tsuyoshi; Peyrin, Thomas (eds.). Advances in Cryptology – ASIACRYPT 2017 – 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3–7, 2017, Proceedings, Part II. Lecture Notes in Computer Science. Vol. 10625. Springer. pp. 241–270. arXiv:1706.06752. doi:10.1007/978-3-319-70697-9_9.

[VSBYSC01-7] Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H. & Chuang, Isaac L. (2001), "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance" (PDF), Nature, 414 (6866): 883–887, arXiv:quant-ph/0112176, Bibcode:2001Natur.414..883V, CiteSeerX 10.1.1.251.8799, doi:10.1038/414883a, PMID 11780055, S2CID 4400832

[LBYP07-8] Lu, Chao-Yang; Browne, Daniel E.; Yang, Tao & Pan, Jian-Wei (2007), "Demonstration of a Compiled Version of Shor's Quantum Factoring Algorithm Using Photonic Qubits" (PDF), Physical Review Letters, 99 (25): 250504, arXiv:0705.1684, Bibcode:2007PhRvL..99y0504L, doi:10.1103/PhysRevLett.99.250504, PMID 18233508, S2CID 5158195

[LWLBJGW07-9] Lanyon, B. P.; Weinhold, T. J.; Langford, N. K.; Barbieri, M.; James, D. F. V.; Gilchrist, A. & White, A. G. (2007), "Experimental Demonstration of a Compiled Version of Shor's Algorithm with Quantum Entanglement" (PDF), Physical Review Letters, 99 (25): 250505, arXiv:0705.1398, Bibcode:2007PhRvL..99y0505L, doi:10.1103/PhysRevLett.99.250505, hdl:10072/21608, PMID 18233509, S2CID 10010619

[10] Lucero, Erik; Barends, Rami; Chen, Yu; Kelly, Julian; Mariantoni, Matteo; Megrant, Anthony; O'Malley, Peter; Sank, Daniel; Vainsencher, Amit; Wenner, James; White, Ted; Yin, Yi; Cleland, Andrew N.; Martinis, John M. (2012). "Computing prime factors with a Josephson phase qubit quantum processor". Nature Physics. 8 (10): 719. arXiv:1202.5707. Bibcode:2012NatPh...8..719L. doi:10.1038/nphys2385. S2CID 44055700.

[11] Martín-López, Enrique; Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (12 October 2012). "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. 6 (11): 773–776. arXiv:1111.4147. Bibcode:2012NaPho...6..773M. doi:10.1038/nphoton.2012.259. S2CID 46546101.

[12] Amico, Mirko; Saleem, Zain H.; Kumph, Muir (2019-07-08). "An Experimental Study of Shor's Factoring Algorithm on IBM Q". Physical Review A. 100 (1): 012305. arXiv:1903.00768. doi:10.1103/PhysRevA.100.012305. ISSN 2469-9926. S2CID 92987546.

[13] Karamlou, Amir H.; Simon, William A.; Katabarwa, Amara; Scholten, Travis L.; Peropadre, Borja; Cao, Yudong (2021-10-28). "Analyzing the performance of variational quantum factoring on a superconducting quantum processor". npj Quantum Information. 7 (1): 156. arXiv:2012.07825. Bibcode:2021npjQI...7..156K. doi:10.1038/s41534-021-00478-z. ISSN 2056-6387. S2CID 229156747.

[14] "Quantum computing motte-and-baileys". Shtetl-Optimized. 2019-12-28. Retrieved 2021-11-15.

[15] Shor, Peter W. (October 1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/S0097539795293172. ISSN 0097-5397. S2CID 2337707.

[16] Kitaev, A. Yu (1995-11-20). "Quantum measurements and the Abelian Stabilizer Problem". arXiv:quant-ph/9511026.

[17] Markov, Igor L.; Saeedi, Mehdi (2012). "Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation". Quantum Information and Computation. 12 (5–6): 361–394. arXiv:1202.6614. Bibcode:2012arXiv1202.6614M. doi:10.26421/QIC12.5-6-1. S2CID 16595181.

[18] Markov, Igor L.; Saeedi, Mehdi (2013). "Faster Quantum Number Factoring via Circuit Synthesis". Phys. Rev. A. 87 (1): 012310. arXiv:1301.3210. Bibcode:2013PhRvA..87a2310M. doi:10.1103/PhysRevA.87.012310. S2CID 2246117.

[:0-19] Nielsen, Michael A.; Chuang, Isaac L. (9 December 2010). Quantum Computation and Quantum Information (PDF) (7th ed.). Cambridge University Press. ISBN 978-1-107-00217-3. Archived (PDF) from the original on 2019-07-11. Retrieved 24 April 2022.

[20] Bernstein, Daniel J.; Heninger, Nadia; Lou, Paul; Valenta, Luke (2017). "Post-quantum RSA" (PDF). International Workshop on Post-Quantum Cryptography. Lecture Notes in Computer Science. 10346: 311–329. doi:10.1007/978-3-319-59879-6_18. ISBN 978-3-319-59878-9. Archived (PDF) from the original on 2017-04-20.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

Number-theoretic algorithms
Primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Pritchard Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp Kunerth
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL; KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system
Italics indicate that algorithm is for numbers of special forms

Conheça Walt Disney World

Shor's algorithm

Procedure

Classical part

Quantum order-finding subroutine

The bottleneck

Discrete logarithms

See also

References

Further reading

External links