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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2017/083}},
      url = {https://eprint.iacr.org/2017/083}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.