**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$.

**Category / Keywords: **public-key cryptography / Shor's algorithm, factoring

**Date: **received 2 Feb 2017, last revised 6 Feb 2017

**Contact author: **amj at juniper net

**Available format(s): **PDF | BibTeX Citation

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

**Version: **20170207:022004 (All versions of this report)

**Short URL: **ia.cr/2017/083

[ Cryptology ePrint archive ]