Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Generating random factored Gaussian integers, easily

Authors: Noah Lebowitz-Lockard and Carl Pomerance
Journal: Math. Comp. 85 (2016), 503-516
MSC (2010): Primary 11416; Secondary 65C10, 11K45
Published electronically: June 23, 2015
MathSciNet review: 3404459
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a (random) polynomial-time algorithm to generate a random Gaussian integer with the uniform distribution among those with norm at most $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.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11416, 65C10, 11K45

Retrieve articles in all journals with MSC (2010): 11416, 65C10, 11K45

Additional Information

Noah Lebowitz-Lockard
Affiliation: Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia 30307
MR Author ID: 1128605

Carl Pomerance
Affiliation: Mathematics Department, Dartmouth College, Hanover, New Hampshire 03755
MR Author ID: 140915

Received by editor(s): July 19, 2013
Received by editor(s) in revised form: April 22, 2014
Published electronically: June 23, 2015
Additional Notes: This paper is based on the 2013 senior thesis of the first author written under the direction of the second author at Dartmouth College. The second author was supported in part by NSF grant DMS-1001180.
Article copyright: © Copyright 2015 American Mathematical Society