{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:37:15Z","timestamp":1776847035985,"version":"3.51.2"},"reference-count":13,"publisher":"American Mathematical Society (AMS)","issue":"297","license":[{"start":{"date-parts":[[2016,6,23]],"date-time":"2016-06-23T00:00:00Z","timestamp":1466640000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We present a (random) polynomial-time algorithm to generate a random Gaussian integer with the uniform distribution among those with norm at most\n \n \n \n N<\/mml:mi>\n N<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , along with its prime factorization. The method generalizes to finding a random ideal in the ring of integers of a quadratic number field together with its prime ideal factorization. We also discuss the analogous problem for higher degree number fields.\n <\/p>","DOI":"10.1090\/mcom\/3000","type":"journal-article","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T09:50:16Z","timestamp":1435053016000},"page":"503-516","source":"Crossref","is-referenced-by-count":1,"title":["Generating random factored Gaussian integers, easily"],"prefix":"10.1090","volume":"85","author":[{"given":"Noah","family":"Lebowitz-Lockard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carl","family":"Pomerance","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2015,6,23]]},"reference":[{"issue":"2","key":"1","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","article-title":"PRIMES is in P","volume":"160","author":"Agrawal, Manindra","year":"2004","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1137\/0217012","article-title":"How to generate factored random numbers","volume":"17","author":"Bach, Eric","year":"1988","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"3","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","volume":"138","author":"Cohen, Henri","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540556400"},{"key":"4","isbn-type":"print","volume-title":"Prime numbers","author":"Crandall, Richard","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387252827","edition":"2"},{"issue":"4","key":"5","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00145-003-0051-5","article-title":"Generating random factored numbers, easily","volume":"16","author":"Kalai, Adam","year":"2003","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"#cr-split#-6.1","unstructured":"E. Landau, \u00dcber die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindestzahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate, Arch. Math. Phys., (3) 13 (1908), 305-312"},{"key":"#cr-split#-6.2","unstructured":"Collected works, Vol. 4, Thales Verlag, Essen, 1986, 59-66."},{"key":"7","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/068","volume-title":"Not always buried deep","author":"Pollack, Paul","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780821848807"},{"key":"8","isbn-type":"print","first-page":"78","article-title":"Highly composite numbers [Proc. London Math. Soc. (2) 14 (1915), 347\u2013409]","author":"Ramanujan, S.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0821820761"},{"key":"9","first-page":"64","article-title":"Approximate formulas for some functions of prime numbers","volume":"6","author":"Rosser, J. Barkley","year":"1962","journal-title":"Illinois J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0019-2082","issn-type":"print"},{"issue":"170","key":"10","doi-asserted-by":"publisher","first-page":"483","DOI":"10.2307\/2007968","article-title":"Elliptic curves over finite fields and the computation of square roots mod \ud835\udc5d","volume":"44","author":"Schoof, Ren\u00e9","year":"1985","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"11","volume-title":"Algebraic number theory","author":"Weiss, Edwin","year":"1963"},{"key":"12","unstructured":"S. Wigert, Sur l\u2019ordre de grandeur du nombre des diviseurs d\u2019un entier, Ark. Math., 3 (1906\/1907), 1\u20139."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-03000-2\/S0025-5718-2015-03000-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-03000-2\/S0025-5718-2015-03000-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:38:37Z","timestamp":1776796717000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-03000-2\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,23]]},"references-count":13,"journal-issue":{"issue":"297","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["S0025-5718-2015-03000-2"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3000","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2015,6,23]]}}}