Paper 2017/083

Shor's Algorithm and Factoring: Don't Throw Away the Odd Orders

Anna Johnston

Abstract

Shor's algorithm factors an integer $N$ in two steps. The quantum step computes the order of $a\bmod{N}$ where $a$ is relatively prime to $N$. The classical step uses this order to factor $N$. Descriptions of the classical step require the order, $s$, to be even and that $a^{s/2}\not\equiv -1\bmod{N}$. If $s$ is odd or $a^{s/2}\equiv -1\bmod{N}$, then the quantum step is repeated. This paper describes how each prime divisor of the order $s$, not just $2$, can be used to factor $N$.

Note: Fixed a dangling sentence at the end of section 5