Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Generating random factored ideals in number fields

Author: Zachary Charles
Journal: Math. Comp. 87 (2018), 2047-2056
MSC (2010): Primary 11Y16; Secondary 68Q25
Published electronically: October 17, 2017
MathSciNet review: 3787402
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a randomized polynomial-time algorithm to generate an ideal and its factorization uniformly at random in a given number field. We do this by generating a random integer and its factorization according to the distribution of norms of ideals at most $N$ in the given number field. Using this randomly generated norm, we can produce a random factored ideal in the ring of algebraic integers uniformly at random among ideals with norm up to $N$, in randomized polynomial time. We also present a variant of this algorithm for generating random factored ideals in function fields.

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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 68Q25

Retrieve articles in all journals with MSC (2010): 11Y16, 68Q25

Additional Information

Zachary Charles
Affiliation: Department of Mathematics, University of Wisconsin-Madison, Madison, Wisconsin 53706
MR Author ID: 1002462

Received by editor(s): December 14, 2016
Received by editor(s) in revised form: February 8, 2017
Published electronically: October 17, 2017
Article copyright: © Copyright 2017 American Mathematical Society