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
DOI: https://doi.org/10.1090/mcom/3283
Published electronically: October 17, 2017
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
Email: zcharles@math.wisc.edu

DOI: https://doi.org/10.1090/mcom/3283
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

American Mathematical Society