{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T08:49:55Z","timestamp":1662194995678},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2007,3]]},"abstract":"\n We give polynomial-time quantum algorithms for three problems from computational algebraic number theory. The first is Pell's equation. Given a positive nonsquare integer\n d<\/jats:italic>\n , Pell's equation is\n x<\/jats:italic>\n 2<\/jats:sup>\n \u2212\n dy<\/jats:italic>\n 2<\/jats:sup>\n = 1 and the goal is to find its integer solutions. Factoring integers reduces to finding integer solutions of Pell's equation, but a reduction in the other direction is not known and appears more difficult. The second problem we solve is the principal ideal problem in real quadratic number fields. This problem, which is at least as hard as solving Pell's equation, is the one-way function underlying the Buchmann--Williams key exchange system, which is therefore broken by our quantum algorithm. Finally, assuming the generalized Riemann hypothesis, this algorithm can be used to compute the class group of a real quadratic number field.\n <\/jats:p>","DOI":"10.1145\/1206035.1206039","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"1-19","source":"Crossref","is-referenced-by-count":77,"title":["Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem"],"prefix":"10.1145","volume":"54","author":[{"given":"Sean","family":"Hallgren","sequence":"first","affiliation":[{"name":"NEC Laboratories America, Inc., Princeton, NJ"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"e_1_2_1_2_1","unstructured":"Buchmann J. 1989. A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. In S\u00e9minaire de th\u00e9orie des nombres (Paris France) 28--41. Buchmann J. 1989. A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. In S\u00e9minaire de th\u00e9orie des nombres (Paris France) 28--41."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Buchmann J. Thiel C. and Williams H. C. 1995. Short representation of quadratic integers. In Computational Algebra and Number Theory Sydney 1992 W. Bosma and A. J. van der Poorten Eds. Mathematics and its Applications vol. 325. Kluwer Academic Publishers 159--185. Buchmann J. Thiel C. and Williams H. C. 1995. Short representation of quadratic integers. In Computational Algebra and Number Theory Sydney 1992 W. Bosma and A. J. van der Poorten Eds. Mathematics and its Applications vol. 325. Kluwer Academic Publishers 159--185.","DOI":"10.1007\/978-94-017-1108-1_12"},{"key":"e_1_2_1_4_1","volume-title":"AB, 1988). Kluwer Acad. Publ.","author":"Buchmann J."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(91)90039-Z"},{"key":"e_1_2_1_6_1","volume-title":"Advances in Cryptology---CRYPTO '89","volume":"435","author":"Buchmann J. A."},{"key":"e_1_2_1_7_1","volume-title":"Graduate Texts in Mathematics","volume":"138","author":"Cohen H.","year":"1993"},{"key":"e_1_2_1_8_1","unstructured":"Ettinger M. H\u00f8yer P. and Knill E. 1999. Hidden subgroup states are almost orthogonal. Tech. rep. quant-ph\/9901034. Ettinger M. H\u00f8yer P. and Knill E. 1999. Hidden subgroup states are almost orthogonal. Tech. rep. quant-ph\/9901034."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780544"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380769"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335392"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378679"},{"key":"e_1_2_1_13_1","unstructured":"Jozsa R. 2003. Notes on Hallgren's efficient quantum algorithm for solving Pell's equation. Tech. rep. quant-ph\/0302134. Jozsa R. 2003. Notes on Hallgren's efficient quantum algorithm for solving Pell's equation. Tech. rep. quant-ph\/0302134."},{"key":"e_1_2_1_14_1","unstructured":"Kuperberg G. 2003. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. Tech. rep. quant-ph\/0302134. Kuperberg G. 2003. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. Tech. rep. quant-ph\/0302134."},{"key":"e_1_2_1_15_1","volume-title":"The Development of the Number Field Sieve. Lecture Notes in Mathematics","volume":"1544","author":"Lenstra A."},{"key":"e_1_2_1_16_1","volume-title":"Journees Arithmetiques, Exeter","author":"Lenstra Jr., H. W.","year":"1980"},{"key":"e_1_2_1_17_1","first-page":"2","article-title":"Solving the Pell equation","volume":"49","author":"Lenstra Jr., H. W.","year":"2002","journal-title":"Notices Amer. Math. Soc."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Moore C."},{"key":"e_1_2_1_19_1","unstructured":"Niven I. Zuckerman H. S. and Montgomery H. L. 1991. An Introduction to the Theory of Numbers Fifth ed. Wiley New York. Niven I. Zuckerman H. S. and Montgomery H. L. 1991. An Introduction to the Theory of Numbers Fifth ed. Wiley New York."},{"key":"e_1_2_1_20_1","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/602382.602408"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298637"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"van Dam W."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/648185.749904"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380759"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Millennial Conference on Number Theory.","volume":"3","author":"Williams H. C.","year":"2000"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1206035.1206039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,20]],"date-time":"2021-02-20T02:58:04Z","timestamp":1613789884000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1206035.1206039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,3]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,3]]}},"alternative-id":["10.1145\/1206035.1206039"],"URL":"http:\/\/dx.doi.org\/10.1145\/1206035.1206039","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2007,3]]}}}