{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T19:03:56Z","timestamp":1767035036347,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":8,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Swedish NCSA, Swedish Armed Forces"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We show that given the order of a single element selected uniformly at random from <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathbb {Z}}_N^*$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msubsup>\n                    <mml:mi>Z<\/mml:mi>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mo>\u2217<\/mml:mo>\n                  <\/mml:msubsup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we can with very high probability, and for any integer <jats:italic>N<\/jats:italic>, efficiently find the complete factorization of <jats:italic>N<\/jats:italic> in polynomial time. This implies that a single run of the quantum part of Shor\u2019s factoring algorithm is usually sufficient. All prime factors of <jats:italic>N<\/jats:italic> can then be recovered with negligible computational cost in a classical post-processing step. The classical algorithm required for this step is essentially due to Miller.<\/jats:p>","DOI":"10.1007\/s11128-021-03069-1","type":"journal-article","created":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T07:05:49Z","timestamp":1623222349000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["On completely factoring any integer efficiently in a single run of an order-finding algorithm"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7061-2374","authenticated-orcid":false,"given":"Martin","family":"Eker\u00e5","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,9]]},"reference":[{"issue":"257","key":"3069_CR1","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1090\/S0025-5718-06-01837-0","volume":"76","author":"DJ Bernstein","year":"2007","unstructured":"Bernstein, D.J., Lenstra, H.W., Pila, J.: Detecting perfect powers by factoring into coprimes. Math. Comput. 76(257), 385\u2013388 (2007)","journal-title":"Math. Comput."},{"issue":"5","key":"3069_CR2","first-page":"522","volume":"7","author":"PS Bourdon","year":"2007","unstructured":"Bourdon, P.S., Williams, H.T.: Sharp probability estimates for Shor\u2019s order finding algorithm. Quantum Inf. Comput. 7(5), 522\u2013550 (2007)","journal-title":"Quantum Inf. Comput."},{"issue":"11","key":"3069_CR3","doi-asserted-by":"publisher","first-page":"2313","DOI":"10.1007\/s10623-020-00783-2","volume":"88","author":"M Eker\u00e5","year":"2020","unstructured":"Eker\u00e5, M.: On post-processing in the quantum algorithm for computing short discrete logarithms. Des. Codes Cryptogr. 88(11), 2313\u20132335 (2020)","journal-title":"Des. Codes Cryptogr."},{"key":"3069_CR4","doi-asserted-by":"crossref","unstructured":"Eker\u00e5, M.: Quantum algorithms for computing general discrete logarithms and orders with tradeoffs. J. Math. Cryptol. 15(1), 359\u2013407 (2021)","DOI":"10.1515\/jmc-2020-0006"},{"key":"3069_CR5","doi-asserted-by":"crossref","unstructured":"Eker\u00e5, M., H\u00e5stad, J.: Quantum algorithms for computing short discrete logarithms and factoring RSA integers. In: PQCrypto, Lecture Notes in Comput. Sci. (LNCS), vol. 10346, Springer, Cham, pp. 347\u2013363 (2017)","DOI":"10.1007\/978-3-319-59879-6_20"},{"key":"3069_CR6","unstructured":"Grosshans, F., Lawson, T., Morain, F., Smith, B.: Factoring safe semiprimes with a single quantum query. ArXiv:1511.04385v3 (2015)"},{"issue":"3","key":"3069_CR7","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/0022-0000(93)90038-X","volume":"47","author":"J H\u00e5stad","year":"1993","unstructured":"H\u00e5stad, J., Schrift, A.W., Shamir, A.: The discrete logarithm modulo a composite hides $$O(n)$$ bits. J. Comput. Syst. Sci. 47(3), 376\u2013404 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"3069_CR8","unstructured":"Johnston, A.M.: Shor\u2019s algorithm and factoring: don\u2019t throw away the odd orders. IACR ePrint Archive 2017\/083 (2017)"},{"key":"3069_CR9","unstructured":"Knill, E.: On Shor\u2019s quantum factor finding algorithm: increasing the probability of success and tradeoffs involving the Fourier transform modulus. Tech. Rep. LAUR-95-3350, Los Alamos National Laboratory (1995)"},{"issue":"3","key":"3069_CR10","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1007\/s11128-014-0910-z","volume":"14","author":"T Lawson","year":"2015","unstructured":"Lawson, T.: Odd orders in Shor\u2019s factoring algorithm. Quantum Inf. Process. 14(3), 831\u2013838 (2015)","journal-title":"Quantum Inf. Process."},{"key":"3069_CR11","unstructured":"Leander, G.: Improving the success probability for Shor\u2019s factoring algorithm. ArXiv:quant-ph\/0208183 (2002)"},{"issue":"4","key":"3069_CR12","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"3069_CR13","unstructured":"Long, D.L.: Random equivalence of factorization and computation of orders. Technical report. Princeton University"},{"issue":"11","key":"3069_CR14","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1038\/nphoton.2012.259","volume":"6","author":"E Mart\u00edn-L\u00f3pez","year":"2012","unstructured":"Mart\u00edn-L\u00f3pez, E., Laing, A., Lawson, T., Alvarez, R., Zhou, X.-Q., O\u2019Brien, J.L.: Experimental realization of Shor\u2019s quantum factoring algorithm using qubit recycling. Nat. Photonics 6(11), 773\u2013776 (2012)","journal-title":"Nat. Photonics"},{"issue":"3","key":"3069_CR15","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","volume":"13","author":"GL Miller","year":"1976","unstructured":"Miller, G.L.: Riemann\u2019s hypothesis and tests for primality. J. Comput. Syst. Sci. 13(3), 300\u2013317 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"3069_CR16","unstructured":"Morain, F., Renault, G., Smith, B.: Deterministic factoring with oracles. ArXiv:1802.08444 (2018)"},{"issue":"3","key":"3069_CR17","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1017\/S0305004100049252","volume":"76","author":"JM Pollard","year":"1974","unstructured":"Pollard, J.M.: Theorems of factorization and primality testing. Math. Proc. Camb. Philos. Soc. 76(3), 521\u2013528 (1974)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"issue":"1","key":"3069_CR18","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","volume":"12","author":"MO Rabin","year":"1980","unstructured":"Rabin, M.O.: Probabilistic algorithm for testing primality. J. Number Theory 12(1), 128\u2013138 (1980)","journal-title":"J. Number Theory"},{"issue":"2","key":"3069_CR19","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest, R.L., Shamir, A., Adleman, L.: A Method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120\u2013126 (1978)","journal-title":"Commun. ACM"},{"key":"3069_CR20","doi-asserted-by":"crossref","unstructured":"Seifert, J.P.: Using fewer qubits in Shor\u2019s factorization algorithm via simultaneous Diophantine approximation. In: CT-RSA, Lecture Notes in Comput. Sci. (LNCS), vol. 2020, Springer, Berlin Heidelberg, pp. 319\u2013327 (2001)","DOI":"10.1007\/3-540-45353-9_24"},{"key":"3069_CR21","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: SFCS, proceedings of the 35th annual symposium on foundations of computer science, IEEE Computer Society, Washington, DC, pp. 124\u2013134 (1994)"},{"issue":"5","key":"3069_CR22","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."},{"key":"3069_CR23","doi-asserted-by":"crossref","unstructured":"Xu, G., Qiu, D., Zou, X., Gruska, J.: Improving the success probability for Shor\u2019s factorization algorithm. In: reversibility and universality. Emergence, complexity and computation, vol. 30, Springer, Cham, pp. 447\u2013462 (2018)","DOI":"10.1007\/978-3-319-73216-9_21"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03069-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03069-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03069-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,5]],"date-time":"2021-07-05T08:24:10Z","timestamp":1625473450000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03069-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["3069"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03069-1","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"type":"print","value":"1570-0755"},{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2021,6]]},"assertion":[{"value":"6 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"205"}}