Editing Shor's algorithm (section)

=== Classical reduction ===
A complete factoring algorithm is possible if we're able to efficiently factor arbitrary <math> N </math> into just two integers <math> p </math> and <math> q </math> greater than 1, since if either <math> p </math> or <math> q </math> are not prime, then the factoring algorithm can in turn be run on those until only primes remain.

A basic observation is that, using [[Euclidean algorithm|Euclid's algorithm]], we can always compute the [[Greatest common divisor|GCD]] between two integers efficiently. In particular, this means we can check efficiently whether <math> N </math> is even, in which case 2 is trivially a factor. Let us thus assume that <math> N </math> is odd for the remainder of this discussion. Afterwards, we can use efficient classical algorithms to check whether <math> N </math> is a [[prime power]].<ref>{{cite journal |last1=Bernstein |first1=Daniel |title=Detecting perfect powers in essentially linear time |journal=Mathematics of Computation |date=1998 |volume=67 |issue=223 |pages=1253–1283 |doi=10.1090/S0025-5718-98-00952-1 }}</ref> For prime powers, efficient classical factorization algorithms exist,<ref>For example, computing the first <math>\log_2(N)</math> roots of <math>N</math>, e.g., with the [[Nth_root#Computing_principal_roots|Newton method]] and checking each integer result for primality ([[AKS primality test]]).</ref> hence the rest of the quantum algorithm may assume that <math> N </math> is not a prime power.

If those easy cases do not produce a nontrivial factor of <math> N </math>, the algorithm proceeds to handle the remaining case. We pick a random integer <math> 2 \leq a < N </math>. A possible nontrivial divisor of <math> N </math> can be found by computing <math> \gcd(a, N) </math>, which can be done classically and efficiently using the [[Euclidean algorithm]]. If this produces a nontrivial factor (meaning <math> \gcd(a, N) \ne 1 </math>), the algorithm is finished, and the other nontrivial factor is <math> N/\gcd(a, N) </math>. If a nontrivial factor was not identified, then this means that <math> N </math> and the choice of <math> a </math> are [[coprime]], so <math>a</math> is contained in the [[multiplicative group of integers modulo n|multiplicative group of integers modulo <math>N</math>]], having a [[multiplicative inverse]] modulo <math>N</math>. Thus, <math>a</math> has a [[multiplicative order]] <math> r </math> modulo <math>N</math>, meaning
: <math>a^r \equiv 1 \bmod N,</math>
and <math>r</math> is the smallest positive integer satisfying this congruence.

The quantum subroutine finds <math>r</math>. It can be seen from the congruence that <math> N </math> [[divides]] <math> a^r - 1 </math>, written <math> N \mid a^r - 1 </math>. This can be factored using [[difference of squares]]:
<math display="block">
 N \mid (a^{r/2} - 1)(a^{r/2} + 1).
</math>
Since we have factored the expression in this way, the algorithm doesn't work for odd <math> r </math> (because <math> a^{r/2} </math> must be an integer), meaning that the algorithm would have to restart with a new <math> a </math>. Hereafter we can therefore assume that <math> r </math> is even. It cannot be the case that <math> N \mid a^{r/2} - 1 </math>, since this would imply <math>a^{r/2} \equiv 1 \bmod N</math>, which would contradictorily imply that <math> r/2 </math> would be the order of <math> a </math>, which was already <math> r </math>. At this point, it may or may not be the case that <math> N \mid a^{r/2} + 1 </math>. If <math>N</math> does not divide <math> a^{r/2} + 1 </math>, then this means that we are able to find a nontrivial factor of <math> N </math>. We compute
<math display="block">
 d = \gcd(N, a^{r/2} - 1).
</math>
If <math> d = 1 </math>, then <math> N \mid a^{r/2} + 1 </math> was true, and a nontrivial factor of <math> N </math> cannot be achieved from <math> a </math>, and the algorithm must restart with a new <math> a </math>. Otherwise, we have found a nontrivial factor of <math> N </math>, with the other being <math> N/d </math>, and the algorithm is finished. For this step, it is also equivalent to compute <math> \gcd(N, a^{r/2} + 1) </math>; it will produce a nontrivial factor if <math> \gcd(N, a^{r/2} - 1) </math> is nontrivial, and will not if it's trivial (where <math> N \mid a^{r/2} + 1 </math>).

The algorithm restated shortly follows: let <math> N </math> be odd, and not a prime power. We want to output two nontrivial factors of <math> N </math>.
# Pick a random number <math> 1 < a < N </math>.
# Compute <math> K = \gcd(a, N) </math>, the [[greatest common divisor]] of <math> a </math> and <math> N </math>.
# If <math> K \neq 1 </math>, then <math>K</math> is a [[nontrivial]] factor of <math> N </math>, with the other factor being <math>N/K</math>, and we are done.
# Otherwise, use the quantum subroutine to find the order <math> r </math> of <math>a</math>.
# If <math> r </math> is odd, then go back to step 1.
# Compute <math>g = \gcd(N, a^{r/2} + 1)</math>. If <math>g </math> is nontrivial, the other factor is <math>N/g</math>, 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.<ref name="siam"/> In practice, a single call to the quantum order-finding subroutine is enough to completely factor <math>N</math> with very high probability of success if one uses a more advanced reduction.<ref name="Ekerå21">{{cite journal |last1=Ekerå |first1=Martin |title=On completely factoring any integer efficiently in a single run of an order-finding algorithm |journal=Quantum Information Processing |date=June 2021 |volume=20 |issue=6 |page=205 |doi=10.1007/s11128-021-03069-1 |arxiv=2007.10044 |bibcode=2021QuIP...20..205E |doi-access=free }}</ref>