{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:29:27Z","timestamp":1760369367418,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319598789"},{"type":"electronic","value":"9783319598796"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59879-6_19","type":"book-chapter","created":{"date-parts":[[2017,6,3]],"date-time":"2017-06-03T16:28:34Z","timestamp":1496507314000},"page":"330-346","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["A Low-Resource Quantum Factoring Algorithm"],"prefix":"10.1007","author":[{"given":"Daniel J.","family":"Bernstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Fran\u00e7ois","family":"Biasse","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michele","family":"Mosca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,4]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","first-page":"355","DOI":"10.4064\/aa-12-4-355-364","volume":"12","author":"MM Artjuhov","year":"1966","unstructured":"Artjuhov, M.M.: Certain criteria for primality of numbers connected with the little Fermat theorem. Acta Arith. 12, 355\u2013364 (1966)","journal-title":"Acta Arith."},{"key":"19_CR2","unstructured":"Barbulescu, R.: Algorithms of discrete logarithm in finite fields. Thesis, Universit\u00e9 de Lorraine, December 2013. https:\/\/tel.archives-ouvertes.fr\/tel-00925228"},{"issue":"2","key":"19_CR3","first-page":"175","volume":"3","author":"S Beauregard","year":"2003","unstructured":"Beauregard, S.: Circuit for Shor\u2019s algorithm using $$2n+3$$ qubits. Quantum Inf. Comput. 3(2), 175\u2013185 (2003)","journal-title":"Quantum Inf. Comput."},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.1103\/PhysRevA.54.1034","volume":"54","author":"D Beckman","year":"1996","unstructured":"Beckman, D., Chari, A.N., Devabhaktuni, S., Preskill, J.: Efficient networks for quantum factoring. Phys. Rev. A 54, 1034\u20131063 (1996)","journal-title":"Phys. Rev. A"},{"issue":"4","key":"19_CR5","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1137\/0218053","volume":"18","author":"CH Bennett","year":"1989","unstructured":"Bennett, C.H.: Time\/space trade-offs for reversible computation. SIAM J. Comput. 18(4), 766\u2013776 (1989)","journal-title":"SIAM J. Comput."},{"issue":"223","key":"19_CR6","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1090\/S0025-5718-98-00952-1","volume":"67","author":"DJ Bernstein","year":"1998","unstructured":"Bernstein, D.J.: Detecting perfect powers in essentially linear time. Math. Comput. 67(223), 1253\u20131283 (1998)","journal-title":"Math. Comput."},{"key":"19_CR7","unstructured":"Bernstein, D.J.: Circuits for integer factorization: a proposal (2001). https:\/\/cr.yp.to\/papers.html#nfscircuit"},{"issue":"1","key":"19_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.04.009","volume":"54","author":"DJ Bernstein","year":"2005","unstructured":"Bernstein, D.J.: Factoring into coprimes in essentially linear time. J. Algorithms 54(1), 1\u201330 (2005)","journal-title":"J. Algorithms"},{"issue":"257","key":"19_CR9","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 Jr., H.W., Pila, J.: Detecting perfect powers by factoring into coprimes. Math. Comput. 76(257), 385\u2013388 (2007)","journal-title":"Math. Comput."},{"key":"19_CR10","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/BFb0091539","volume-title":"The development of the number field sieve","author":"JP Buhler","year":"1993","unstructured":"Buhler, J.P., Lenstra Jr., H.W., Pomerance, C.: Factoring integers with the number field sieve. In: Lenstra, A.K., Lenstra Jr., H.W. (eds.) The development of the number field sieve. LNM, vol. 1554, pp. 50\u201394. Springer, Heidelberg (1993). doi:10.1007\/BFb0091539"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. In: Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 454. The Royal Society (1998)","DOI":"10.1098\/rspa.1998.0164"},{"issue":"3","key":"19_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF00198464","volume":"6","author":"D Coppersmith","year":"1993","unstructured":"Coppersmith, D.: Modifications to the number field sieve. J. Cryptol. 6(3), 169\u2013180 (1993)","journal-title":"J. Cryptol."},{"issue":"6","key":"19_CR13","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W Diffie","year":"1976","unstructured":"Diffie, W., Hellman, M.: New directions in cryptography. IEEE Trans. Inf. Soc. 22(6), 644\u2013654 (1976)","journal-title":"IEEE Trans. Inf. Soc."},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1137\/0406010","volume":"6","author":"D Gordon","year":"1993","unstructured":"Gordon, D.: Discrete logarithms in GF(p) using the number field sieve. SIAM J. Discret. Math. 6, 124\u2013138 (1993)","journal-title":"SIAM J. Discret. Math."},{"issue":"15\u201316","key":"19_CR15","first-page":"1338","volume":"14","author":"D Gottesman","year":"2014","unstructured":"Gottesman, D.: Fault-tolerant quantum computation with constant overhead. Quantum Inf. Comput. 14(15\u201316), 1338\u20131372 (2014). https:\/\/arxiv.org\/pdf\/1310.2984","journal-title":"Quantum Inf. Comput."},{"key":"19_CR16","unstructured":"Grosshans, F., Lawson, T., Morain, F., Smith, B.: Factoring safe semiprimes with a single quantum query (2015). http:\/\/arxiv.org\/abs\/1511.04385"},{"key":"19_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-642-14623-7_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"T Kleinjung","year":"2010","unstructured":"Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thom\u00e9, E., Bos, J.W., Gaudry, P., Kruppa, A., Montgomery, P.L., Osvik, D.A., Riele, H., Timofeev, A., Zimmermann, P.: Factorization of a 768-bit RSA modulus. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 333\u2013350. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-14623-7_18"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Lenstra, A.K., Lenstra Jr., H.W., Manasse, M.S., Pollard, J.M.: The number field sieve. In: STOC 1990: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 564\u2013572. ACM, New York (1990)","DOI":"10.1145\/100216.100295"},{"issue":"3","key":"19_CR19","doi-asserted-by":"publisher","first-page":"649","DOI":"10.2307\/1971363","volume":"126","author":"HW Lenstra Jr","year":"1987","unstructured":"Lenstra Jr., H.W.: Factoring integers with elliptic curves. Ann. Math. (2) 126(3), 649\u2013673 (1987)","journal-title":"Ann. Math. (2)"},{"key":"19_CR20","unstructured":"Menezes, A., Sarkar, P., Singh, S.: Challenges with assessing the impact of NFS advances on the security of pairing-based cryptography. In: Proceedings of Mycrypt 2016 (2016, to appear). https:\/\/eprint.iacr.org\/2016\/1102"},{"key":"19_CR21","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/BFb0091536","volume-title":"The development of the number field sieve","author":"JM Pollard","year":"1993","unstructured":"Pollard, J.M.: Factoring with cubic integers. In: Lenstra, A.K., Lenstra Jr., H.W. (eds.) The development of the number field sieve. LNM, vol. 1554, pp. 4\u201310. Springer, Heidelberg (1993). doi:10.1007\/BFb0091536"},{"issue":"2","key":"19_CR22","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.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120\u2013126 (1978)","journal-title":"Commun. ACM"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1098\/rsta.1993.0139","volume":"345","author":"O Schirokauer","year":"1993","unstructured":"Schirokauer, O.: Discrete logarithms and local units. Philos. Trans. Phys. Sci. Eng. 345, 409\u2013423 (1993)","journal-title":"Philos. Trans. Phys. Sci. Eng."},{"key":"19_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/3-540-45353-9_24","volume-title":"Topics in Cryptology\u2014CT-RSA 2001","author":"J-P Seifert","year":"2001","unstructured":"Seifert, J.-P.: Using fewer qubits in Shor\u2019s factorization algorithm via simultaneous diophantine approximation. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 319\u2013327. Springer, Heidelberg (2001). doi:10.1007\/3-540-45353-9_24"},{"issue":"5","key":"19_CR25","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P Shor","year":"1997","unstructured":"Shor, P.: 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."},{"issue":"2","key":"19_CR26","first-page":"184","volume":"6","author":"Y Takahashi","year":"2006","unstructured":"Takahashi, Y., Kunihiro, N.: A quantum circuit for Shor\u2019s factoring algorithm using $$2n+2$$ qubits. Quantum Inf. Comput. 6(2), 184\u2013192 (2006)","journal-title":"Quantum Inf. Comput."},{"key":"19_CR27","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1103\/PhysRevA.54.147","volume":"54","author":"V Vedral","year":"1996","unstructured":"Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arithmetic operations. Phys. Rev. A 54, 147\u2013153 (1996)","journal-title":"Phys. Rev. A"}],"container-title":["Lecture Notes in Computer Science","Post-Quantum Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59879-6_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:29:38Z","timestamp":1710343778000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-59879-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319598789","9783319598796"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59879-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"4 June 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PQCrypto","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Post-Quantum Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Utrecht","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 June 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pqcrypto2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/2017.pqcrypto.org\/conference\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}