Cryptology ePrint Archive: Report 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$.

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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]