Skip to content
Home

Shor's algorithm: quantum integer factoring and cryptography impact

Shor's algorithm is a quantum algorithm that factors integers and finds discrete orders in polynomial time, with important implications for public-key cryptography and the development of large-scale quantum computers.

Author: Created: Updated:

Shor's algorithm is a landmark quantum algorithm introduced by Peter Shor in the mid-1990s. It provides a method to factor large integers or, equivalently, to compute the order of an element modulo N. The algorithm showed that a sufficiently powerful quantum computer could solve an important problem much faster than known classical algorithms, raising profound practical and theoretical questions.

Image gallery

1 Image
Asymmetric encryption scheme
en.wikipedia.org · CC BY 4.0

Problem and goal

The algorithm addresses integer factorization: given a composite number N, find nontrivial prime factors. This task—finding prime factors—is the basis of widely used public-key schemes. Shor transformed factoring into an instance of order-finding, which a quantum processor can solve efficiently by exploiting superposition and interference.

How it works (high level)

At a conceptual level the quantum part performs period or order finding using the quantum Fourier transform. After preparing superposed states and applying a modular exponentiation operation, a quantum measurement yields information about the period. That information is then processed classically to recover factors. The major logical steps are:

  • Reduce factoring to finding the order r of a random integer a modulo N.
  • Use a quantum circuit to create a superposition and compute periodic sequence values.
  • Apply the quantum Fourier transform and measure to obtain data related to r.
  • Use classical postprocessing (continued fractions, gcd) to extract factors.

Complexity and implications

Shor's algorithm runs in polynomial time in the number of digits of N, a dramatic improvement over the best known classical methods whose running time grows superpolynomially for large N. Because the security of widely deployed systems such as RSA and other public-key schemes depends on the practical difficulty of factoring, a fully scalable quantum computer running Shor's algorithm would undermine many current cryptographic systems and has driven interest in quantum-resistant alternatives.

History, experiments and limitations

Since its discovery, Shor's algorithm has been demonstrated on small numbers in laboratory quantum devices, but scaling to the sizes needed to break modern keys requires large, fault-tolerant quantum machines and significant error correction overhead. Progress in qubit quality, coherence times and scalable architectures remains essential before the algorithm poses a real threat to deployed cryptography.

Uses, distinctions and further reading

Beyond its immediate cryptographic implications, Shor's algorithm is a central example in the study of quantum algorithms and complexity theory, illustrating how quantum resources can change computational difficulty classes. The result has motivated work in post-quantum cryptography and in alternative quantum algorithms for problems like discrete logarithms. For introductory surveys and technical expositions see further resources.

Properties

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

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

Expiration

The basic idea is that one can factorize back to the determination of the order. This determination can be done effectively using the quantum Fourier transform. One therefore often divides the algorithm into a classical part to reduce the problem and a quantum part that efficiently solves the residual problem.

Classic part

  1. Choose a number xwith {\displaystyle 1<x<n}.
  2. Determine the {\displaystyle ggT}{\displaystyle (x} , {\displaystyle n)}(for example, using the Euclidean algorithm). If the result is not equal to 1, return this as the solution and terminate. Otherwise, proceed to the next step.
  3. Using the quantum part (see below), determine the order rof xin the prime residue class group ({\mathbb Z}/n{\mathbb Z})^{\times }(the smallest r\in {\mathbb {N}}, such that x^{r}\equiv 1({\textrm {mod}}\;n)). Step 2 ensured that such an rexists.
  4. Start over at 1 if:
    1. ris odd, or
    2. x^{{r/2}}\equiv -1({\textrm {mod}}\;n).
  5. Return {\textrm {ggT}}(x^{{r/2}}-1,n)as the solution.

Solution in the last step

Consider the product ( x^{{r/2}}-1) - ( x^{{r/2}}+1) = x^{r}-1. We know after step 3 that holds: {\displaystyle x^{r}-1\equiv 0\mod n}, that it does not hold: {\displaystyle x^{r/2}+1\equiv \ 0\mod n}(Step 4) and that does not hold: {\displaystyle x^{r/2}-1\equiv \ 0\mod n}(step 3, since is rthe smallest number with {\displaystyle x^{r}-1\equiv \ 0\mod n}and {r/2}<rholds), from which it follows that ncontains x^{{r/2}}-1nontrivial divisors of ; the Euclidean algorithm for computing the {\displaystyle ggT}yields these divisors in polynomial time.

Number of iterations for the partial invention

The probability of obtaining a divisor given a random choice of x is at least 1-1/2^{{k-1}}, where kthe number of distinct prime factors of n(not equal to 2). For example, if n is composed of only two prime factors, one solution is obtained with probability 1/2 per pass, so the probability of failure after tsteps is only 2^{{-t}}.

Quantum Part

  1. Determine qas a power of 2 with n^{2}\leq q<2n^{2}.
  2. Initialize the first quantum register (input register) with the superposition (see qubit) of all states {\displaystyle a{\bmod {q}}}( ais a number less than q). This leads to the state:
     {\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 {\displaystyle x^{a}{\bmod {n}}}. The result is the state:
     {\displaystyle {\frac {1}{q^{1/2}}}\sum _{a=0}^{q-1}|a\rangle \ |x^{a}{\bmod {n}}\rangle }.
  4. On the first register, perform the quantum Fourier transform where:
     QFT\left(|a\rangle \right)={\frac {1}{q^{{1/2}}}}\sum _{{c=0}}^{{q-1}}e^{{2\pi iac/q}}\ |c\rangle
    such that results in:
     {\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. Perform a measurement (take the contents of the registers). The probability for the state {\displaystyle \left|c,x^{k}{\bmod {n}}\right\rangle }with is given by0<k<r:
     \left|{\frac {1}{q}}\ \sum _{{a:x^{a}\equiv x^{k}}}e^{{2\pi iac/q}}\right|_{{}}^{2}. Here, the relation {\displaystyle a\equiv k\mod r}or {\displaystyle a=br+k}, so that we can write:
     \left|{\frac {1}{q}}\ \sum _{{b}}e^{{2\pi i\left(br+k\right)c/q}}\right|_{{}}^{2}By amplification, this discrete function has characteristic maxima for values of a variable d\in {\mathbb {Z}}, which is the relation
     \left|{\frac {c}{q}}-{\frac {d}{r}}\right|\leq {\frac {1}{2q}}. It can be shown that for the given relations of {\displaystyle q,r}and there is nat most one such value at fixed cThus, rcomputed if dand rare divisor-irrelevant. (The probability for this case is at least ϕ {\frac {\phi (r)}{3r}}or Ω \Omega \!\left({\frac {1}{\log \log r}}\right), that is, we get rwith high probability after {\displaystyle O(\log \log r)}repetitions).
  6. Return the computed value {\displaystyle r^{\prime }} if it is indeed the order of x, otherwise repeat the experiment.

Related articles

Author

AlegsaOnline.com Shor's algorithm: quantum integer factoring and cryptography impact

URL: https://en.alegsaonline.com/art/89988

Share

Sources