Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Generating random factored ideals in number fields
HTML articles powered by AMS MathViewer

by Zachary Charles PDF
Math. Comp. 87 (2018), 2047-2056 Request permission

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
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
  • Email: zcharles@math.wisc.edu
  • Received by editor(s): December 14, 2016
  • Received by editor(s) in revised form: February 8, 2017
  • Published electronically: October 17, 2017
  • © Copyright 2017 American Mathematical Society
  • Journal: Math. Comp. 87 (2018), 2047-2056
  • MSC (2010): Primary 11Y16; Secondary 68Q25
  • DOI: https://doi.org/10.1090/mcom/3283
  • MathSciNet review: 3787402