# Shor's factoring algorithm Shor's algorithm computes the period of periodic functions. for example $f(x)=a^x\bmod N$ satisfies $f(x)=f(x+r)$ for $r$ the order of $a$ modulo $N$ i.e., $a^r\equiv 1\bmod N$. $f$ has period $r$ and this algorithm computes it. The goal is to find a factor of $N$. steps: 1) Pick random $a<N$ 2) if $\gcd(a,N)>1$ then we have a factor of $N$ otherwise continue 3) find the order $r$ of $a\bmod N$ i.e., $a^r\equiv 1\bmod N$ with Shor's algorithm. 4) If $r$ is odd, stop and start for new $a$ 5) If $r$ is even, we have $a^r-1=(a^{r/2}-1)(a^{r/2}+1)$ and $N|(a^r-1)$ i.e., $N \mid (a^{r/2}-1)(a^{r/2}+1)$. compute $\gcd(a^{r/2}-1,N)$ and $\gcd(a^{r/2}+1,N)$. note that we need smaller value than $a^r$ because $\gcd(a^r,N)=N$ and so give no information on factors. ## How to find the period r of a function efficiently? Let $Q$ be a power 2 s.t. $N^2\le Q<2N^2$ . Using Hadamard gates prepare superposition of computation basis up to $Q$ then clone them to 2nd register and compute the gate of $|x\rangle\mapsto|a^x\bmod N\rangle$ , measure the 2nd register containing the powers to get $a^{j_0}\bmod N$ and the . The first register collapses to $\frac{1}{\sqrt L}\sum_{\ell=0}^{L-1}|j_0+\ell r\rangle$ where $L\approx Q/r$. Next, we apply $QFT_Q$ to $\frac{1}{\sqrt L}\sum_{\ell=0}^{L-1}|j_0+\ell r\rangle$ . A reminder, $QFT_Q|j\rangle=\frac{1}{\sqrt Q}\sum_{c=0}^{Q-1}e^{2\pi i jc/Q}|c\rangle$ .So, $ \begin{align} QFT_Q\bigg(\frac{1}{\sqrt L}\sum_{\ell=0}^{L-1}|j_0+\ell r\rangle\bigg)&=\frac{1}{\sqrt {LQ}}\sum_{\ell=0}^{L-1}\bigg(\sum_{c=0}^{Q-1}e^{2\pi i (j_0+\ell r)c/Q}|c\rangle\bigg) \\ & =\frac{1}{\sqrt {LQ}}\sum_{c=0}^{Q-1}\bigg(\sum_{\ell=0}^{L-1}e^{2\pi i (j_0+\ell r)c/Q}|c\rangle\bigg) \end{align} $ the amplitude of $|c\rangle$ becomes $\sum_{\ell=0}^{L-1}e^{2\pi i (j_0+\ell r)c/Q}$ and $e^{2\pi i j_0c/Q}$ does not affect the amplitude of $|c\rangle$ and so get be ignored. The amplitude which are large are those that the terms $e^{2\pi i \ell rc/Q}$ for $\ell=0,1,..,Q$ points to the same direction so they accumulate and not cancel each other. if all points in the direction of 1 then, $e^{2\pi i \ell rc/Q}=1$ and $rc/Q\approx k$ for $k$ integer i.e., $c\approx Qk/r$. The $QFT_Q$ amplifies the amplitudes of $\frac{Q}{r},\frac{2Q}{r},..$ The register containing the QFT is measured and we get $c\approx Qk/r$. Bu choosing value for $Q$ (at begining) and the fact that $r<N$ we can reconstruct the fraction $Qk/r$ and from there compute efficiently $r$ classically using [[Continued Fractions]]. Reference: - [Quantum Algorithms forthe Discrete LogarithmProblem (MA Thesis)](https://repositum.tuwien.at/handle/20.500.12708/18830) - [[@Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer]] ## Created 2026-06-09 12:20