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

Short URL: ia.cr/2017/083

[ Cryptology ePrint archive ]
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8838148713111877, "perplexity": 2020.6614779463548}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-39/segments/1568514577478.95/warc/CC-MAIN-20190923172009-20190923194009-00012.warc.gz"}