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
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Shor's algorithmfactoring
- Contact author(s)
- amj @ juniper net
- History
- 2017-02-07: revised
- 2017-02-06: received
- See all versions
- Short URL
- https://ia.cr/2017/083
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/083,
author = {Anna Johnston},
title = {Shor's Algorithm and Factoring: Don't Throw Away the Odd Orders},
howpublished = {Cryptology {ePrint} Archive, Paper 2017/083},
year = {2017},
url = {https://eprint.iacr.org/2017/083}
}
