# Shor algorithm

The Shor algorithm is an algorithm from the mathematical branch of number theory that uses quantum computer science . It calculates a nontrivial divisor of a composite number on a quantum computer and thus belongs to the class of factorization methods .

The Shor algorithm cannot yet be used for practically relevant tasks, since up to now (as of 2020) there are no sufficiently large and low-error quantum computers available. A number of binary digits (i. E., ) To factor, a quantum computer requires a quantum register , the size of at least grows linearly with the number of binary digits. Shor's original algorithm requires 3n qubits , the best known variant manages with 2n + 3 qubits. These numbers apply to an ideal (error-free) quantum computer. In practice it is necessary to use quantum error correction methods. Then by a (large, but constant in n ) factor M more physical qubits are required, where M depends very strongly on the error rate and the error correction code used. It is estimated that 10 to 100 million qubits are required for a 2048-bit number (in the absence of errors it would only be a few thousand). For example, a research group at the US company IBM used a quantum computer with seven qubits in 2001 to break down the number 15 into the factors 5 and 3. ${\ displaystyle N}$${\ displaystyle n}$ ${\ displaystyle N <2 ^ {n}}$

The Shor algorithm is very important for cryptography because it finds a nontrivial divisor essentially faster than classical algorithms : While these require subexponential, but significantly higher than polynomial runtime , the Shor algorithm only has polynomial runtime . This represents a danger, for example, for the RSA cryptosystems that are often used for encrypted data transmission , the security of which is based precisely on the assumption that there is no factoring method with a polynomial runtime.

The algorithm was published in 1994 by Peter Shor , who was then employed by AT&T Bell Laboratories . The work is entitled Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer . This also describes a second algorithm for calculating the discrete logarithm , which is also referred to as the Shor algorithm. In general, however, this term is used for the factorization procedure.

## properties

The Shor algorithm is a probabilistic algorithm . In some cases, depending on the number of repetitions, it leads to no result; the algorithm thus belongs to the class of Monte Carlo algorithms .

• Input: A composite number .${\ displaystyle n}$
• Output: A non-trivial factor of .${\ displaystyle n}$
• Runtime: gate operations.${\ displaystyle O \ left ((\ log \, n) ^ {3} \ right)}$

## procedure

The basic idea is that factorization can be reduced to determining the order . This determination can be carried out effectively with the aid of the quantum Fourier transform . The algorithm is therefore often divided into a classic part to reduce the problem and a quantum part that efficiently solves the remaining problem .

### Classic part

1. Pick a number with .${\ displaystyle x}$${\ displaystyle 1
2. Find the , (e.g. using the Euclidean algorithm ). If the result is not 1, return this as the solution and terminate. Otherwise go to the next step.${\ displaystyle gcd}$${\ displaystyle (x}$${\ displaystyle n)}$
3. Determine with the help of the quantum part (see below) the order of in the prime residue class group (the smallest such that ). Step 2 made sure that one exists.${\ displaystyle r}$${\ displaystyle x}$ ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times}}$${\ displaystyle r \ in \ mathbb {N}}$${\ displaystyle x ^ {r} \ equiv 1 ({\ textrm {mod}} \; n)}$${\ displaystyle r}$
4. Start again at 1 if:
1. ${\ displaystyle r}$ is odd, or
2. ${\ displaystyle x ^ {r / 2} \ equiv -1 ({\ textrm {mod}} \; n)}$.
5. Give back as a solution.${\ displaystyle {\ textrm {ggT}} (x ^ {r / 2} -1, n)}$

#### Solution in the last step

Consider the product ( ) * ( ) = . After step 3 we know that: that does not apply: (step 4) and that does not apply: (step 3, since the smallest number with is and applies), from which it follows that contains nontrivial factors of ; the Euclidean algorithm for calculating the supplies these divisors in polynomial time. ${\ displaystyle x ^ {r / 2} -1}$${\ displaystyle x ^ {r / 2} +1}$${\ displaystyle x ^ {r} -1}$${\ displaystyle x ^ {r} -1 \ equiv 0 \ mod n}$${\ displaystyle x ^ {r / 2} +1 \ equiv \ 0 \ mod n}$${\ displaystyle x ^ {r / 2} -1 \ equiv \ 0 \ mod n}$${\ displaystyle r}$${\ displaystyle x ^ {r} -1 \ equiv \ 0 \ mod n}$${\ displaystyle {r / 2} ${\ displaystyle x ^ {r / 2} -1}$${\ displaystyle n}$${\ displaystyle gcd}$

#### Number of iterations for the part invention

The probability of obtaining a factor by randomly choosing is at least , where the number of mutually different prime factors is (not equal to 2). If, for example, is composed of only two prime factors, one gets a solution with a probability of 1/2 per run, so the probability of failure after steps is only . ${\ displaystyle x}$${\ displaystyle 1-1 / 2 ^ {k-1}}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle t}$${\ displaystyle 2 ^ {- t}}$

### Quantum part

1. Determine as a power of 2 with .${\ displaystyle q}$${\ displaystyle n ^ {2} \ leq q <2n ^ {2}}$
2. Initialize the first quantum register (input register) with the superposition (see qubit ) of all states ( is a number smaller than ). This results in the state: .${\ displaystyle a {\ bmod {q}}}$${\ displaystyle a}$${\ displaystyle q}$
${\ displaystyle {\ frac {1} {q ^ {1/2}}} \ sum _ {a = 0} ^ {q-1} | a \ rangle \ | 0 \ rangle}$
3. Initialize the second register (output register) with the superposition of the states . The result is the state: .${\ displaystyle x ^ {a} {\ bmod {n}}}$
${\ displaystyle {\ frac {1} {q ^ {1/2}}} \ sum _ {a = 0} ^ {q-1} | a \ rangle \ | x ^ {a} {\ bmod {n} } \ rangle}$
4. Leads to the first register the quantum Fourier transformation through, wherein: so that we have: .
${\ displaystyle QFT \ left (| a \ rangle \ right) = {\ frac {1} {q ^ {1/2}}} \ sum _ {c = 0} ^ {q-1} e ^ {2 \ pi iac / q} \ | c \ rangle}$

${\ displaystyle {\ frac {1} {q}} \ \ sum _ {a = 0} ^ {q-1} \ \ sum _ {c = 0} ^ {q-1} e ^ {2 \ pi iac / q} \ | c \ rangle \ | x ^ {a} {\ bmod {n}} \ rangle}$
5. Take a measurement (read the contents of the registers). The probability of the state with given by: . For this the relationship or applies , so that we can write: This discrete function has characteristic maxima for values ​​of a variable that satisfy the relationship through amplification . It can be shown that for the given relationships of and there is at most one such value for fixed . This can be used to calculate if and are relatively prime. (The probability for this case is at least or , that is, we get with a high probability after repetitions.)${\ displaystyle \ left | c, x ^ {k} {\ bmod {n}} \ right \ rangle}$${\ displaystyle 0
${\ displaystyle \ left | {\ frac {1} {q}} \ \ sum _ {a: x ^ {a} \ equiv x ^ {k}} e ^ {2 \ pi iac / q} \ right | _ {} ^ {2}}$${\ displaystyle a \ equiv k \ mod r}$${\ displaystyle a = br + k}$
${\ displaystyle \ left | {\ frac {1} {q}} \ \ sum _ {b} e ^ {2 \ pi i \ left (br + k \ right) c / q} \ right | _ {} ^ {2}}$${\ displaystyle d \ in \ mathbb {Z}}$
${\ displaystyle \ left | {\ frac {c} {q}} - {\ frac {d} {r}} \ right | \ leq {\ frac {1} {2q}}}$${\ displaystyle q, r}$${\ displaystyle n}$${\ displaystyle c}$${\ displaystyle r}$${\ displaystyle d}$${\ displaystyle r}$${\ displaystyle {\ frac {\ phi (r)} {3r}}}$${\ displaystyle \ Omega \! \ left ({\ frac {1} {\ log \ log r}} \ right)}$${\ displaystyle r}$${\ displaystyle O (\ log \ log r)}$
6. Return the calculated value if it is actually the order of , otherwise repeat the experiment.${\ displaystyle r ^ {\ prime}}$${\ displaystyle x}$

## Individual evidence

1. a b Craig Gidney, Martin Ekerå: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits . May 23, 2019, Tables 1 and 2 , arxiv : 1905.09749 (English).
2. Lieven MK Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood and Isaac L. Chuang: Experimental realization of an order-finding algorithm with an NMR quantum computer. In: Nature , 414/2001, pp. 883-887, doi: 10.1038 / 414883a
3. Peter W. Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. In: SIAM Journal on Computing , 26/1997, pp. 1484–1509, arxiv : quant-ph / 9508027