# 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 \mid (a^{r/2}-1)(a^{r/2}+1)$. compute $\gcd(a^{r/2}-1,N)$ and $\gcd(a^{r/2}+1,N)$ at least one of them will result in non-trivial factor. Reference: [Quantum Algorithms forthe Discrete LogarithmProblem (MA Thesis)](https://repositum.tuwien.at/handle/20.500.12708/18830) ## Created 2026-06-09 12:20